Physical Education Lessons (Codeforces 915E)
Tags: Implement, sortings

This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:There are n days left before the end of the term (numbered from 1 to n), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers l, r and k:  If k = 1, then all days from l to r (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days;  If k = 2, then all days from l to r (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days. Help Alex to determine the number of working days left after each order!

Input: The first line contains one integer n, and the second line — one integer q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) — the number of days left before the end of the term, and the number of orders, respectively.Then q lines follow, i-th line containing three integers li, ri and ki representing i-th order (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2).

Output: Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.


Sample Inputs:
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2

Sample Outputs:
2
0
2
3
1
4

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedSet(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 200

    def _build(self, a=None) -> None:
        """"""
        if a is None:
            a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size:size * (i + 1) // bucket_size] for i in range(bucket_size)]

    def __init__(self, a: Iterable[T]=[]) -> None:
        """"""
        a = list(a)
        if not all((a[i] < a[i + 1] for i in range(len(a) - 1))):
            a = sorted(set(a))
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i:
                yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i):
                yield j

    def __len__(self) -> int:
        return self.size

    def __repr__(self) -> str:
        return 'SortedSet' + str(self.a)

    def __str__(self) -> str:
        s = str(list(self))
        return '{' + s[1:len(s) - 1] + '}'

    def _find_bucket(self, x: T) -> List[T]:
        """"""
        for a in self.a:
            if x <= a[-1]:
                return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def add(self, x: T) -> bool:
        """"""
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return True
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return False
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()
        return True

    def discard(self, x: T) -> bool:
        """"""
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x:
            return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0:
            self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        """"""
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        """"""
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        """"""
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        """"""
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]

    def __getitem__(self, x: int) -> T:
        """"""
        if x < 0:
            x += self.size
        if x < 0:
            raise IndexError
        for a in self.a:
            if x < len(a):
                return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        """"""
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        """"""
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans
n = int(input())
q = int(input())
ans = []
ans0 = n
d = dict()
now = 0
s = SortedSet([])
for _ in range(q):
    (l, r, t) = map(int, input().split())
    if t == 1:
        if not now:
            ans0 -= r - l + 1
            s.add(r)
            now += 1
            d[r] = l
        else:
            f = 0
            c = s.index(l)
            while c < now:
                r1 = s[c]
                if not r1:
                    break
                l1 = d[r1]
                if l1 <= l <= r <= r1:
                    f = 1
                    break
                if r < l1:
                    break
                if l <= l1 <= r <= r1:
                    ans0 += r1 - l1 + 1
                    r = r1
                    d[r] = l
                    ans0 -= r - l + 1
                    f = 1
                    break
                ans0 += r1 - l1 + 1
                s.discard(r1)
                now -= 1
                if l1 <= l <= r1 <= r:
                    l = l1
            if not f:
                ans0 -= r - l + 1
                s.add(r)
                now += 1
                d[r] = l
    elif now:
        c = s.index(l)
        while c < now:
            r1 = s[c]
            if not r1:
                break
            l1 = d[r1]
            if r < l1:
                break
            if l1 <= l <= r <= r1:
                ans0 += r - l + 1
                if l1 < l:
                    s.add(l - 1)
                    now += 1
                    d[l - 1] = l1
                if r < r1:
                    d[r1] = r + 1
                else:
                    s.discard(r1)
                    now -= 1
                break
            elif l <= l1 <= r <= r1:
                ans0 += r1 - l1 + 1
                l1 = r + 1
                if l1 <= r1:
                    d[r1] = l1
                    ans0 -= r1 - l1 + 1
                else:
                    s.discard(r1)
                    now -= 1
                break
            s.discard(r1)
            now -= 1
            ans0 += r1 - l1 + 1
            if l1 < l:
                r1 = l - 1
                ans0 -= r1 - l1 + 1
                s.add(r1)
                now += 1
                d[r1] = l1
                c += 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedSet(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 300

    def _build(self, a=None) -> None:
        """"""
        if a is None:
            a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size:size * (i + 1) // bucket_size] for i in range(bucket_size)]

    def __init__(self, a: Iterable[T]=[]) -> None:
        """"""
        a = list(a)
        if not all((a[i] < a[i + 1] for i in range(len(a) - 1))):
            a = sorted(set(a))
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i:
                yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i):
                yield j

    def __len__(self) -> int:
        return self.size

    def __repr__(self) -> str:
        return 'SortedSet' + str(self.a)

    def __str__(self) -> str:
        s = str(list(self))
        return '{' + s[1:len(s) - 1] + '}'

    def _find_bucket(self, x: T) -> List[T]:
        """"""
        for a in self.a:
            if x <= a[-1]:
                return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def add(self, x: T) -> bool:
        """"""
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return True
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return False
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()
        return True

    def discard(self, x: T) -> bool:
        """"""
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x:
            return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0:
            self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        """"""
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        """"""
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        """"""
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        """"""
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]

    def __getitem__(self, x: int) -> T:
        """"""
        if x < 0:
            x += self.size
        if x < 0:
            raise IndexError
        for a in self.a:
            if x < len(a):
                return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        """"""
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        """"""
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans
n = int(input())
q = int(input())
ans = []
ans0 = n
d = dict()
now = 0
s = SortedSet([])
for _ in range(q):
    (l, r, t) = map(int, input().split())
    if t == 1:
        if not now:
            ans0 -= r - l + 1
            s.add(r)
            now += 1
            d[r] = l
        else:
            f = 0
            c = s.index(l)
            while c < now:
                r1 = s[c]
                if not r1:
                    break
                l1 = d[r1]
                if l1 <= l <= r <= r1:
                    f = 1
                    break
                if r < l1:
                    break
                if l <= l1 <= r <= r1:
                    ans0 += r1 - l1 + 1
                    r = r1
                    d[r] = l
                    ans0 -= r - l + 1
                    f = 1
                    break
                ans0 += r1 - l1 + 1
                s.discard(r1)
                now -= 1
                if l1 <= l <= r1 <= r:
                    l = l1
            if not f:
                ans0 -= r - l + 1
                s.add(r)
                now += 1
                d[r] = l
    elif now:
        c = s.index(l)
        while c < now:
            r1 = s[c]
            if not r1:
                break
            l1 = d[r1]
            if r < l1:
                break
            if l1 <= l <= r <= r1:
                ans0 += r - l + 1
                if l1 < l:
                    s.add(l - 1)
                    now += 1
                    d[l - 1] = l1
                if r < r1:
                    d[r1] = r + 1
                else:
                    s.discard(r1)
                    now -= 1
                break
            elif l <= l1 <= r <= r1:
                ans0 += r1 - l1 + 1
                l1 = r + 1
                if l1 <= r1:
                    d[r1] = l1
                    ans0 -= r1 - l1 + 1
                else:
                    s.discard(r1)
                    now -= 1
                break
            s.discard(r1)
            now -= 1
            ans0 += r1 - l1 + 1
            if l1 < l:
                r1 = l - 1
                ans0 -= r1 - l1 + 1
                s.add(r1)
                now += 1
                d[r1] = l1
                c += 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedSet(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 200

    def _build(self, a=None) -> None:
        """"""
        if a is None:
            a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size:size * (i + 1) // bucket_size] for i in range(bucket_size)]

    def __init__(self, a: Iterable[T]=[]) -> None:
        """"""
        a = list(a)
        if not all((a[i] < a[i + 1] for i in range(len(a) - 1))):
            a = sorted(set(a))
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i:
                yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i):
                yield j

    def __len__(self) -> int:
        return self.size

    def __repr__(self) -> str:
        return 'SortedSet' + str(self.a)

    def __str__(self) -> str:
        s = str(list(self))
        return '{' + s[1:len(s) - 1] + '}'

    def _find_bucket(self, x: T) -> List[T]:
        """"""
        for a in self.a:
            if x <= a[-1]:
                return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def add(self, x: T) -> bool:
        """"""
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return True
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return False
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()
        return True

    def discard(self, x: T) -> bool:
        """"""
        if self.size == 0:
            return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x:
            return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0:
            self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        """"""
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        """"""
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        """"""
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        """"""
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]

    def __getitem__(self, x: int) -> T:
        """"""
        if x < 0:
            x += self.size
        if x < 0:
            raise IndexError
        for a in self.a:
            if x < len(a):
                return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        """"""
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        """"""
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans
n = int(input())
q = int(input())
ans = []
ans0 = n
d = dict()
now = 0
s = SortedSet([])
for _ in range(q):
    (l, r, t) = map(int, input().split())
    if t == 1:
        if not now:
            ans0 -= r - l + 1
            s.add(r)
            now += 1
            d[r] = l
        else:
            f = 0
            c = s.index(l)
            while c < now:
                r1 = s[c]
                if not r1:
                    break
                l1 = d[r1]
                if l1 <= l <= r <= r1:
                    f = 1
                    break
                if r < l1:
                    break
                if l <= l1 <= r <= r1:
                    ans0 += r1 - l1 + 1
                    r = r1
                    d[r] = l
                    ans0 -= r - l + 1
                    f = 1
                    break
                ans0 += r1 - l1 + 1
                s.discard(r1)
                now -= 1
                if l1 <= l <= r1 <= r:
                    l = l1
            if not f:
                ans0 -= r - l + 1
                s.add(r)
                now += 1
                d[r] = l
    elif now:
        c = s.index(l)
        while c < now:
            r1 = s[c]
            if not r1:
                break
            l1 = d[r1]
            if r < l1:
                break
            if l1 <= l <= r <= r1:
                ans0 += r - l + 1
                if l1 < l:
                    s.add(l - 1)
                    now += 1
                    d[l - 1] = l1
                if r < r1:
                    d[r1] = r + 1
                else:
                    s.discard(r1)
                    now -= 1
                break
            elif l <= l1 <= r <= r1:
                ans0 += r1 - l1 + 1
                l1 = r + 1
                if l1 <= r1:
                    d[r1] = l1
                    ans0 -= r1 - l1 + 1
                else:
                    s.discard(r1)
                    now -= 1
                break
            s.discard(r1)
            now -= 1
            ans0 += r1 - l1 + 1
            if l1 < l:
                r1 = l - 1
                ans0 -= r1 - l1 + 1
                s.add(r1)
                now += 1
                d[r1] = l1
                c += 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))