Submission #684551

#	Time	Username	Problem	Language	Result	Execution time	Memory
684551		Nursik	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5047 ms	524288 KiB

street_lamps

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <random>
#include <chrono>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 1e6 + 1, maxm = 80;
const ll mod = 1e9 + 7, inf = 1e9, blck = 500;
const ld eps = 1e-9;
 
int n, q;
string s, type;
set<int> setik;
ll rng(){
    return ((rand() << 15) + rand());
}
struct tnode{
    ll pos, sum, y, prior;
    tnode *l, *r;
    tnode(int x, int z){
        pos = x;
        y = z;
        sum = z;
        prior = rng();
        l = r = nullptr;
    }
};
struct treap{
    ll getsum(tnode *v){
        return (v ? v->sum : 0);
    }
    void pull(tnode *v){
        v->sum = getsum(v->l) + v->y + getsum(v->r);
    }
    pair<tnode*, tnode*> split(tnode* &v, int val){
        if (v == nullptr)
            return {v, v};
        if (v->pos < val){
            pair<tnode*, tnode*> splitted = split(v->r, val);
            v->r = splitted.f;
            pull(v);
            return mp(v, splitted.s);
        }
        else{
            pair<tnode*, tnode*> splitted = split(v->l, val);
            v->l = splitted.f;
            pull(v);
            return mp(splitted.f, v);
        }
    }
    tnode *merge(tnode *l, tnode *r){
        if (l == nullptr || r == nullptr){
            return (l ? l : r);
        }
        if (l->prior > r->prior){
            l->r = merge(l->r, r);
            pull(l);
            return l;
        }
        else{
            r->l = merge(l, r->l);
            pull(r);
            return r;
        }
    }
    int is(tnode* &v, int x, ll z){
        if (v == nullptr)
            return 0;
        if (v->pos == x){
            v->sum += z;
            v->y += z;
            return 1;
        }
        int ok = 0;
        if (v->pos < x){
            ok = is(v->r, x, z);
        }
        else{
            ok = is(v->l, x, z);
        }
        pull(v);
        return ok;
    }
    void insval(tnode* &v, int x, int z){
        if (is(v, x, z)){
            return;
        }
        pair<tnode*, tnode*> split1 = split(v, x);
        tnode* cur = new tnode(x, z);
        v = merge(merge(split1.f, cur), split1.s);
        return; 
    }
    int get(int r, tnode* &v){
        if (v == nullptr)
            return 0;
        if (v->pos <= r){
            return getsum(v->l) + v->y + get(r, v->r);
        }
        else{
            return get(r, v->l);
        }
    }
} tree;
struct seg_tree{
    tnode *t[maxn << 2];
    void upd(int l, int r, int l2, int r2, int add, int v = 1, int tl = 1, int tr = n){
        if (l > tr || r < tl)
            return;
        if (l <= tl && tr <= r){
            tree.insval(t[v], l2, add);
            tree.insval(t[v], r2, -add);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(l, r, l2, r2, add, v + v, tl, tm);
        upd(l, r, l2, r2, add, v + v + 1, tm + 1, tr);
    }
    int get(int l, int r, int v = 1, int tl = 1, int tr = n){
        if (l > tr || r < tl)
            return 0;
        if (tl == tr){
            return tree.get(r, t[v]);
        }
        int tm = (tl + tr) / 2;
        int add = tree.get(r, t[v]);
        if (l <= tm){
            add += get(l, r, v + v, tl, tm);
        }
        else{
            add += get(l, r, v + v + 1, tm + 1, tr);
        }
        return add;
    }
} tree2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    cin >> n >> q;
    cin >> s;
    s = '#'+ s;
    setik.insert(0);
    setik.insert(n + 1);
    for (int i = 1; i <= n; ++i){
        if (s[i] == '0'){
            setik.insert(i);
        }
    }
    for (int x, l, r, i = 1; i <= q; ++i){
        cin >> type;
        if (type == "toggle"){
            int x;
            cin >> x;
            if (s[x] == '0'){
                setik.erase(x);
                auto it = setik.upper_bound(x);
                r = *it;
                l = *(--it) + 1;
               // cout << l << " " << x << " " << x << " " << r << '\n';
                tree2.upd(l, x, x, r, -i);
                s[x] = '1';
            }
            else{
                auto it = setik.upper_bound(x);
                r = *it;
                l = *(--it) + 1;
               // cout << l << " " << r << '\n';
                setik.insert(x);
                tree2.upd(l, x, x, r, i);
                s[x] = '0';
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            int add = 0;
            auto it = setik.lower_bound(l);
            if (*it > r - 1){
                add = 1;
            }
          //  cout << tree2.get(l, r - 1) << '\n';
            cout << tree2.get(l, r - 1) + add * i << '\n';
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:180:14: warning: unused variable 'x' [-Wunused-variable]
  180 |     for (int x, l, r, i = 1; i <= q; ++i){
      |              ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20