Submission #1102701

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102701	2024-10-18T16:18:08 Z	Requiem	Street Lamps (APIO19_street_lamps)	C++17	80 / 100	1018 ms	383948 KB

street_lamps

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "streetlamp"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Street lamp:

Có n trạm dừng kết nối n + 1 cái stop.
ta biết trạng thái của cái stop

Ta có q truy vấn:
- query a b: Từ 1 đến i, ta, tổng các thời điểm mà ta có thể đi từ a b
- toggle i: lật ngược vị trí i

subtask 1: n <= 100, q <= 100. Chạy n * q^2.

subtask 2: b = a + 1.
Tức là ta chỉ quan tâm vị trí i được bật bao nhiêu lần.
cái này bỏ vào prefix sum.

subtask 3: Khi bật nút i, nó sẽ luôn bật.
Nó là bài toán dsu điển hình, tức là 2 đỉnh sẽ không bao giờ bị disconnect.

subtask 4:
Ta toggle trước xong mới đến các truy vấn.
Giả sử ta dsu rollback, khi ta thêm 1 cạnh vào, nó
sẽ liên kết các tplt bên trong đó.

Giả sử nó nối đoạn [1...3] với [4..5] thì ta thêm hình chữ nhật [1...3], [4...5]
với trọng số là thời gian t.

Khi này ta sẽ tính offline bằng sweepline. Giả sử ta cần truy vấn a, b: thì ta chỉ cần truy vấn đoạn [a, b].
Ta có n log n sự kiện thì có tối đa n log n hình chữ nhật,

subtask 5:
Bây giờ ta cần phải xử lý online. Làm thế nào cơ chứ.
Nếu ta cắm BIT2D vào thì nó cũng vẫn sẽ là N log ^ 3 N.
Ta chia các hcn thành 2 loại:
- Đã kết thúc
- Còn thời gian.
**/

const int MAXN = 3e5 + 9;
int n, q, u, v;
char lamp[MAXN];

struct query{
    string type;
    int l, r, u;
} Query[MAXN];

struct DSU{
    struct DSUnode{
        int par;
        int sz;
        int mn;
        int mx;
    };
    vector<DSUnode> D;
    vector<array<int, 6>> changes;
    int small_to_large, path_compression, roll_back;
    DSU(int sz = 0, int _small_to_large = 1, int _path_compression = 1, int _roll_back = 0){
        D.resize(sz + 9);
        small_to_large = _small_to_large;
        path_compression = _path_compression;
        roll_back = _roll_back;
        FOR(i, 0, D.size() - 1){
            D[i].par = i;
            D[i].sz = 1;
            D[i].mn = D[i].mx = i;
        }
    }

    void rollback(){
        if (changes.size() == 0) return;
        array<int, 6> tp = changes.back();
        int u = tp[0];
        int v = tp[1];
        D[u].sz -= D[v].sz;
        D[v].par = v;
        D[u].mn = tp[2], D[u].mx = tp[3];
        D[v].mn = tp[4], D[v].mx = tp[5];
        changes.pop_back();
    }
    int root(int u){
        if (D[u].par == u) return u;
        else {
            int p = root(D[u].par);
            if (path_compression) D[u].par = p;
            return p;
        }
    }

    bool unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (small_to_large and D[u].sz < D[v].sz) swap(u, v);
            D[u].sz += D[v].sz;
            D[v].par = u;
            if (roll_back) changes.pb({u, v, D[u].mn, D[u].mx, D[v].mn, D[v].mx});;

            D[u].mx = max(D[u].mx, D[v].mx);
            D[u].mn = min(D[u].mn, D[v].mn);
            return true;
        }
        return false;
    }
};
namespace subtask1{
    bool check(){
        return n <= 100 and q <= 100;
    }


    DSU timelineDSU[103];
    void solve(){
        FOR(i, 1, q){
            timelineDSU[i] = DSU(n + 1);
            FOR(j, 1, n){
                if (lamp[j] == '1') {
                    timelineDSU[i].unite(j, j + 1);
                }
            }

            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                lamp[u] = ((lamp[u] == '0') ? '1' : '0');
            }
            else{
                int ans = 0;
                FOR(j, 1, i){
                    if (timelineDSU[j].root(Query[i].l) == timelineDSU[j].root(Query[i].r)) {
                        ans++;
                    }
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask2{
    bool check(){
        FOR(i, 1, q){
            if (Query[i].type == "query" and Query[i].l != Query[i].r - 1) return false;
        }
        return true;
    }

    int pre[300003], lastTime[MAXN];
    void solve(){
        FOR(i, 1, n){
            pre[i] = 0;
            if (lamp[i] == '1') lastTime[i] = 1;
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                if (lamp[u] == '1') {
                    pre[u] += i - lastTime[u] + 1;
                    lastTime[u] = 0;
                    lamp[u] = '0';
                }
                else{
                    lastTime[u] = i + 1;
                    lamp[u] = '1';
                }
            }
            if (Query[i].type == "query"){
                int ans = pre[Query[i].l];
                if (lamp[Query[i].l] == '1'){
                    ans += i - lastTime[Query[i].l] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask3{
    char tmp[300005];
    bool check(){
        FOR(i, 1, n){
            tmp[i] = lamp[i];
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and tmp[Query[i].u] == '1') return false;
            if (Query[i].type == "toggle") tmp[Query[i].u] = '1';
        }
        return true;
    }

    /**
    Voi 2 dinh a va b, ta can tim thoi gian dau tien ma hai thang do ket hop lam 1. Cái này có thể giải bằng
    chặt nhị phân song song.

    Dùng reachability Tree.
    **/

    vector<int> reachability[MAXN * 2];
    int edgeTime[MAXN * 2];

    int P[22][MAXN * 2], depth[MAXN * 2];

    void dfs(int u, int p){
        P[0][u] = p;
        for(auto v: reachability[u]){
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int lca(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
            if (P[i][u] != -1 and depth[P[i][u]] >= depth[v]) u = P[i][u];
        }

        if (u == v) return u;

        FORD(i, 20, 0){
            if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]) {
                u = P[i][u];
                v = P[i][v];
            }
        }

        return P[0][u];
    }

    void solve(){
        int small_to_large = 0;
        int path_compression = 1;
        int roll_back = 0;
        DSU D(2 * n + 9, small_to_large, path_compression, roll_back);
        int cntEdge = n + 1;
        FOR(i, 1, n){
            if (lamp[i] == '1') {
                ++cntEdge;
                edgeTime[cntEdge] = 1;

                int r1 = D.root(i);
                int r2 = D.root(i + 1);

                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;
                    reachability[cntEdge].pb(r2);
                }

            }

        }


        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                ++cntEdge;
                edgeTime[cntEdge] = i + 1;
                int r1 = D.root(u);
                int r2 = D.root(u + 1);
                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;

                    reachability[cntEdge].pb(r2);
                }
            }
        }

        FORD(i, 2 * n + 3, 1){
            if (P[0][i] == 0) dfs(i, -1);
        }

        FOR(i, 1, 20){
            FOR(j, 1, 2 * n + 3){
                if (P[i - 1][j] == -1) P[i][j] = -1;
                P[i][j] = P[i - 1][P[i - 1][j]];
            }
        }

        FOR(i, 1, q){
            int ans = 0;
            if (Query[i].type == "query"){
                int l = Query[i].l;
                int r = Query[i].r;
                if (D.root(l) == D.root(r)){
                    int acs = lca(l, r);
                    if (i >= edgeTime[acs]) ans += i - edgeTime[acs] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

struct BinaryIndexedTree{
    vector<int> BIT;
    BinaryIndexedTree(int sz = 0){
        BIT.resize(sz + 9);
    }

    void update(int id, int val){
        for(int i = id; i < BIT.size(); i += i & (-i)){
            BIT[i] += val;
        }
    }

    int get(int id){
        int res = 0;
        for(int i = id; i > 0; i -= i & (-i)){
            res += BIT[i];
        }
        return res;
    }

    void updateRange(int l, int r, int val){
        update(l, val);
        update(r + 1, -val);
    }
};
namespace subtask4{
    bool check(){
        bool alreadyQuery = 0;
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and alreadyQuery) return false;
            if (Query[i].type == "query") alreadyQuery = true;
        }
        return true;
    }

    struct rectangle{
        int L, R, B, T, val;
        rectangle(int _L = 0, int _R = 0, int _B = 0, int _T = 0, int _v = 0){
            L = _L;
            R = _R;
            B = _B;
            T = _T;
            val = _v;
        }

    };

    vector<rectangle> rect;
    vector<iii> points;

    struct event{
        int x, type, l, r;
        event(int _x = 0, int _type = 0, int _l = 0, int _r = 0): x(_x), type(_type), l(_l), r(_r) {}
    };
    vector<int> valRectangleInclude(vector<rectangle> rect, vector<iii> points){
        vector<int> result(points.size());
        vector<event> events;
        BinaryIndexedTree BIT(300005);

        FOR(i, 0, (int) rect.size() - 1){
            events.pb(event(rect[i].L, rect[i].val, rect[i].B, rect[i].T));
            events.pb(event(rect[i].R + 1,-rect[i].val, rect[i].B, rect[i].T));
        }

        FOR(i, 0, (int) points.size() - 1){
            events.pb(event(points[i].se.fi, 0, points[i].fi, points[i].se.se));
        }

        sort(events.begin(), events.end(), [&](const event &a, const event &b){
             return a.x < b.x;
        });

        for(int i = 0, j = 0; i < events.size(); i = j){
            j = i;
            while(j < events.size() and events[j].x == events[i].x){
                if (events[j].type != 0) {
                    BIT.updateRange(events[j].l, events[j].r, events[j].type);
                }
                j++;
            }

            j = i;
            while(j < events.size() and events[j].x == events[i].x){
                 if (events[j].type == 0) {
                    result[events[j].l] = BIT.get(events[j].r);
                 }
                 j++;
            }
        }
        return result;
    }


    /**
    Moi lan ta them canh vao, ta chac no se tao 1 thanh phan lien thong moi, ta chi quan tam rang la
    2 doan ma no dang o thoi.
    Khi ta add 2 thang vao thi chac chan no se la hai thang tien de tao thanh 2 thang lon hon.
    **/

    vector<int> dsuRollback[MAXN << 2];
    DSU D;

    void addEvent(int nn, int l, int r, int u, int v, int e){
        if (l >= u and r <= v){
            dsuRollback[nn].pb(e);
            return;
        }
        if (l > v or r < u) return;
        int mid = (l + r) >> 1;
        addEvent(nn << 1, l, mid, u, v, e);
        addEvent(nn << 1 | 1, mid + 1, r, u, v, e);
    }

    void go(int nn, int l, int r){
        int sz = D.changes.size();
        for(auto p: dsuRollback[nn]){
            D.unite(p, p + 1);
            int rt = D.root(p);
            rect.pb(rectangle(D.D[rt].mn, p, p + 1, D.D[rt].mx, r - l + 1));
        }

        if (l != r){
            int mid = (l + r) >> 1;
            go(nn << 1, l, mid);
            go(nn << 1 | 1, mid + 1, r);
        }

        while(D.changes.size() > sz) D.rollback();


    }

    int lastTime[MAXN];
    void solve(){
        int startAsking = q + 1;
        FOR(i, 1, q){
            if (Query[i].type == "query") {
                startAsking = i;
                break;
            }
        }

        D = DSU(n + 1, 1, 0, 1);
        DSU current = DSU(n + 1, 1, 1, 0);

        FOR(i, 1, n){
            if (lamp[i] == '1') lastTime[i] = 1;
        }

        FOR(i, 1, startAsking - 1){
            int u = Query[i].u;
            if (lamp[u] == '1'){
                addEvent(1, 1, startAsking, lastTime[u], i, u);
                lastTime[u] = 0;
                lamp[u] = '0';
            }
            else{
                lamp[u] = '1';
                lastTime[u] = i + 1;
            }
        }

        FOR(i, 1, n){
            if (lastTime[i] > 0) addEvent(1, 1, startAsking, lastTime[i], startAsking, i);
        }

        go(1, 1, startAsking);

        FOR(i, 1, n){
            if (lamp[i] == '1') current.unite(i, i + 1);
        }


        FOR(i, startAsking, q){
            points.pb({i - startAsking, ii(Query[i].l, Query[i].r)});
        }

//        for(int i = 0; i < rect.size(); i++){
//            cerr << rect[i].val << endl;
//        }

        vector<int> result = valRectangleInclude(rect, points);

        FOR(i, startAsking, q){
            int l = Query[i].l;
            int r = Query[i].r;
            if (current.root(l) == current.root(r)){
                result[i - startAsking] += i - startAsking;
            }
            cout << result[i - startAsking] << endl;
        }


    }
}

namespace subtask5{
    bool check(){
        return true;
    }
    int RAND(int l, int r){
        return rand() % (r - l + 1) + l;
    }
    struct TreapNode{
        int key = 0, val = 0, pr = 0, sz = 0, sum = 0;
        TreapNode *leftChild, *rightChild;

        TreapNode(int _key = 0, int _val = 0){
            key = _key;
            val = _val;
            sum = _val;
            pr = RAND(1, 3e5);
            sz = 1;
            leftChild = rightChild = NULL;
        }


    };

    typedef TreapNode* Treap;

    int getSize(Treap root){
        if (root == NULL) return 0;
        return root->sz;
    }

    int getSum(Treap root){
        if (root == NULL) return 0;
        return root->sum;

    }
    void calc(Treap root){
        if (root == NULL) return;
        root->sz = getSize(root->leftChild) + getSize(root->rightChild) + 1;
        root->sum = getSum(root->leftChild) + getSum(root->rightChild) + root->val;
    }

    void Split(Treap root, Treap &l, Treap &r, int key){
        if (root == NULL){
            l = r = NULL;
            return;
        }


        if (root->key <= key){
            l = root;
            Split(root->rightChild, l->rightChild, r, key);
        }
        else{
            r = root;
            Split(root->leftChild, l, r->leftChild, key);
        }

        calc(root);
    }

    void Merge(Treap &root, Treap l, Treap r){
        if (!l or !r) {
            root = (!l) ? r : l;
            return;
        }

        if (l->pr < r->pr) {
            Merge(l->rightChild, l->rightChild, r);
            root = l;
        }
        else {
            Merge(r->leftChild, l, r->leftChild);
            root = r;
        }

        calc(root);
    }
    bool findKey(Treap root, int key){
        if (root == NULL) return false;

        if (root->key == key) return true;
        if (root->key > key) return findKey(root->leftChild, key);
        if (root->key < key) return findKey(root->rightChild, key);
    }
    void insertKey(Treap &root, int key, int val){
        Treap res, l, r;
        Split(root, l, r, key - 1);
        Merge(l, l, new TreapNode(key, val));
        Merge(l, l, r);
        root = l;
    }

    void updateKey(Treap &root, int key, int value){
        if (root->key == key) root->val += value;

        if (root->key < key) updateKey(root->rightChild, key, value);
        if (root->key > key) updateKey(root->leftChild, key, value);

        calc(root);
    }

    void goUpdateKey(Treap &root, int key, int value){
        if (!findKey(root, key)){
            insertKey(root, key, value);
            return;
        }
        updateKey(root, key, value);
    }



    int get(Treap &root, int key){
        Treap l, r;
        Split(root, l, r, key);
        int res = getSum(l);
        Merge(l, l, r);
        root = l;
        return res;

    }

    void go(Treap root){
        if (root == NULL) return;
        go(root->leftChild);
        cerr << root->val << ' ' ;
        go(root->rightChild);
    }

    Treap segtree[MAXN << 2];

    void update(int nn, int l, int r, int L, int R, int B, int T, int val){
        if (l >= L and r <= R){
            goUpdateKey(segtree[nn], B, val);
            goUpdateKey(segtree[nn], T + 1, -val);
            return;
        }

        if (l > R or r < L) return;
        int mid = (l + r) >> 1;
        update(nn << 1, l, mid, L, R, B, T, val);
        update(nn << 1 | 1, mid + 1, r, L, R, B, T, val);
    }

    void getPoint(int nn, int l, int r, int x1, int y1, int &res){
        res +=get(segtree[nn], y1);
        if (l == r) return;

        int mid = (l + r) >> 1;

        if (x1 <= mid) getPoint(nn << 1, l, mid, x1, y1, res);
        else getPoint(nn << 1 | 1, mid + 1, r, x1, y1, res);

    }

    Treap root;
    char lamp[MAXN];

    struct Query{
        string type;
        int u, l, r;
    } Query[MAXN];

    struct BinaryIndexedTree{
        vector<int> BIT;
        BinaryIndexedTree(int sz = 0){
            BIT.resize(sz + 9, 0);
        }

        int get(int id){
            int res = 0;
            for(int i = id; i > 0; i -= i & (-i)){
                res += BIT[i];
            }
            return res;
        }

        void update(int id, int val){
            for(int i = id; i < BIT.size(); i += i & (-i)){
                BIT[i] += val;
            }
        }

        int getRange(int l, int r){
            return get(r) - get(l - 1);
        }

        int furthestLeft(int x){
            int l = 1, r = x, res = -1;
            while(l <= r){
                int mid = (l + r) >> 1;
                if (getRange(mid, x) == x - mid + 1){
                    res = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            return res;
        }

        int furthestRight(int x){
            int l = x, r = BIT.size() - 1, res = -1;
            while(l <= r){
                int mid = (l + r) >> 1;
                if (getRange(x, mid) == mid - x + 1){
                    res = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            return res;
        }
        //get(l - 1) + l + 1 == get(r) - r. Tìm vị trí 1 đầu tiên thỏa.
    };

    void solve(){

        BinaryIndexedTree BIT(n);
        FOR(i, 1, n){
            if (lamp[i] == '1') {
                BIT.update(i, 1);
                int l = BIT.furthestLeft(i);
    //            cout << l << ' ' << i << endl;
                update(1, 1, n, l, i, i, i, -1);
            }
        }



        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                if (lamp[u] == '0'){
                    lamp[u] = '1';
                    BIT.update(u, 1);
                    int L = BIT.furthestLeft(u);
                    int R = BIT.furthestRight(u);
    //                cout<< L << ' ' << u << ' ' << u << ' '<< R << ' ' << -(i + 1) << endl;
                    update(1, 1, n, L, u, u, R, -(i + 1));
                    int res = 0;
                    getPoint(1, 1, n, 1, 5, res);
    //                cout << res << endl;
                }
                else{
                    lamp[u] = '0';
                    int L = BIT.furthestLeft(u);
                    int R = BIT.furthestRight(u);
                    update(1, 1, n, L, u, u, R, +i + 1);
                    BIT.update(u, -1);
                }
            }
            else{
                int l = Query[i].l;
                int r = Query[i].r - 1;
                int res = 0;
                getPoint(1, 1, n, l, r, res);
                if (lamp[l] == '1' and lamp[r] == '1' and BIT.furthestRight(l) >= r){
                    res += i + 1;
                }
                cout << res << endl;
            }
        }

    }

}
main()
{
    fast;
    srand(time(NULL));
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".trau.out","w",stdout);
    }
    cin >> n >> q;
    FOR(i, 1, n){
        cin >> lamp[i];
    }
    FOR(i, 1, q){
        cin >> Query[i].type;
        if (Query[i].type == "toggle"){
            cin >> Query[i].u;

        }
        else if (Query[i].type == "query"){
            cin >> Query[i].l >> Query[i].r;
        }
    }

    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
    if (subtask4::check()) return subtask4::solve(), 0;
    if (subtask5::check()) return subtask5::solve(), 0;
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

street_lamps.cpp: In constructor 'DSU::DSU(int, int, int, int)':
street_lamps.cpp:9:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DSU::DSUnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
   83 |         FOR(i, 0, D.size() - 1){
      |             ~~~~~~~~~~~~~~~~~~   
street_lamps.cpp:83:9: note: in expansion of macro 'FOR'
   83 |         FOR(i, 0, D.size() - 1){
      |         ^~~
street_lamps.cpp: In member function 'void BinaryIndexedTree::update(int, int)':
street_lamps.cpp:330:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  330 |         for(int i = id; i < BIT.size(); i += i & (-i)){
      |                         ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'std::vector<int> subtask4::valRectangleInclude(std::vector<subtask4::rectangle>, std::vector<std::pair<int, std::pair<int, int> > >)':
street_lamps.cpp:395:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  395 |         for(int i = 0, j = 0; i < events.size(); i = j){
      |                               ~~^~~~~~~~~~~~~~~
street_lamps.cpp:397:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  397 |             while(j < events.size() and events[j].x == events[i].x){
      |                   ~~^~~~~~~~~~~~~~~
street_lamps.cpp:405:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  405 |             while(j < events.size() and events[j].x == events[i].x){
      |                   ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void subtask4::go(int, int, int)':
street_lamps.cpp:450:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 6> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  450 |         while(D.changes.size() > sz) D.rollback();
      |               ~~~~~~~~~~~~~~~~~^~~~
street_lamps.cpp: In function 'void subtask5::insertKey(subtask5::TreapNode*&, int, int)':
street_lamps.cpp:604:15: warning: unused variable 'res' [-Wunused-variable]
  604 |         Treap res, l, r;
      |               ^~~
street_lamps.cpp: In member function 'void subtask5::BinaryIndexedTree::update(int, int)':
street_lamps.cpp:696:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  696 |             for(int i = id; i < BIT.size(); i += i & (-i)){
      |                             ~~^~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:784:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  784 | main()
      | ^~~~
street_lamps.cpp: In function 'bool subtask5::findKey(subtask5::Treap, int)':
street_lamps.cpp:602:5: warning: control reaches end of non-void function [-Wreturn-type]
  602 |     }
      |     ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:789:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  789 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:790:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  790 |         freopen(TASKNAME".trau.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	75088 KB	Output is correct
2	Correct	15 ms	75088 KB	Output is correct
3	Correct	13 ms	75088 KB	Output is correct
4	Correct	16 ms	75088 KB	Output is correct
5	Correct	18 ms	75088 KB	Output is correct
6	Correct	16 ms	75088 KB	Output is correct
7	Correct	15 ms	75088 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	75848 KB	Output is correct
2	Correct	74 ms	75848 KB	Output is correct
3	Correct	70 ms	75908 KB	Output is correct
4	Correct	83 ms	76104 KB	Output is correct
5	Correct	91 ms	76616 KB	Output is correct
6	Correct	69 ms	75848 KB	Output is correct
7	Correct	93 ms	75848 KB	Output is correct
8	Correct	86 ms	77224 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	118096 KB	Output is correct
2	Correct	20 ms	118264 KB	Output is correct
3	Correct	19 ms	118096 KB	Output is correct
4	Correct	18 ms	118352 KB	Output is correct
5	Correct	212 ms	149396 KB	Output is correct
6	Correct	307 ms	149576 KB	Output is correct
7	Correct	423 ms	149776 KB	Output is correct
8	Correct	823 ms	160272 KB	Output is correct
9	Correct	95 ms	118860 KB	Output is correct
10	Correct	102 ms	119124 KB	Output is correct
11	Correct	103 ms	119112 KB	Output is correct
12	Correct	123 ms	136776 KB	Output is correct
13	Correct	794 ms	160324 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	78416 KB	Output is correct
2	Correct	16 ms	78428 KB	Output is correct
3	Correct	17 ms	78672 KB	Output is correct
4	Correct	22 ms	78928 KB	Output is correct
5	Correct	194 ms	131396 KB	Output is correct
6	Correct	435 ms	191196 KB	Output is correct
7	Correct	657 ms	273792 KB	Output is correct
8	Correct	1018 ms	383948 KB	Output is correct
9	Correct	396 ms	178604 KB	Output is correct
10	Correct	378 ms	178848 KB	Output is correct
11	Correct	369 ms	178660 KB	Output is correct
12	Correct	382 ms	178852 KB	Output is correct
13	Correct	354 ms	178612 KB	Output is correct
14	Correct	367 ms	178844 KB	Output is correct
15	Correct	125 ms	136616 KB	Output is correct
16	Correct	788 ms	160328 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	75088 KB	Output is correct
2	Correct	15 ms	75088 KB	Output is correct
3	Correct	13 ms	75088 KB	Output is correct
4	Correct	16 ms	75088 KB	Output is correct
5	Correct	18 ms	75088 KB	Output is correct
6	Correct	16 ms	75088 KB	Output is correct
7	Correct	15 ms	75088 KB	Output is correct
8	Correct	65 ms	75848 KB	Output is correct
9	Correct	74 ms	75848 KB	Output is correct
10	Correct	70 ms	75908 KB	Output is correct
11	Correct	83 ms	76104 KB	Output is correct
12	Correct	91 ms	76616 KB	Output is correct
13	Correct	69 ms	75848 KB	Output is correct
14	Correct	93 ms	75848 KB	Output is correct
15	Correct	86 ms	77224 KB	Output is correct
16	Correct	18 ms	118096 KB	Output is correct
17	Correct	20 ms	118264 KB	Output is correct
18	Correct	19 ms	118096 KB	Output is correct
19	Correct	18 ms	118352 KB	Output is correct
20	Correct	212 ms	149396 KB	Output is correct
21	Correct	307 ms	149576 KB	Output is correct
22	Correct	423 ms	149776 KB	Output is correct
23	Correct	823 ms	160272 KB	Output is correct
24	Correct	95 ms	118860 KB	Output is correct
25	Correct	102 ms	119124 KB	Output is correct
26	Correct	103 ms	119112 KB	Output is correct
27	Correct	123 ms	136776 KB	Output is correct
28	Correct	794 ms	160324 KB	Output is correct
29	Correct	15 ms	78416 KB	Output is correct
30	Correct	16 ms	78428 KB	Output is correct
31	Correct	17 ms	78672 KB	Output is correct
32	Correct	22 ms	78928 KB	Output is correct
33	Correct	194 ms	131396 KB	Output is correct
34	Correct	435 ms	191196 KB	Output is correct
35	Correct	657 ms	273792 KB	Output is correct
36	Correct	1018 ms	383948 KB	Output is correct
37	Correct	396 ms	178604 KB	Output is correct
38	Correct	378 ms	178848 KB	Output is correct
39	Correct	369 ms	178660 KB	Output is correct
40	Correct	382 ms	178852 KB	Output is correct
41	Correct	354 ms	178612 KB	Output is correct
42	Correct	367 ms	178844 KB	Output is correct
43	Correct	125 ms	136616 KB	Output is correct
44	Correct	788 ms	160328 KB	Output is correct
45	Incorrect	60 ms	75336 KB	Output isn't correct
46	Halted	0 ms	0 KB	-