제출 #684572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684572		Nursik	가로등 (APIO19_street_lamps)	C++14	100 / 100	554 ms	71968 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 (((ll)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.s;
            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->y += z;
            pull(v);
            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);
     /*   if (z == -4){
            cout << "kek\n";
            cout << x << '\n';
            cout << split1.f->pos << '\n';
            cout << split1.f->sum << " " << split1.f->y << '\n';
            cout << "aloha\n";
            cout << split1.s->pos << '\n';
            cout << split1.s->sum << " " << split1.s->y << '\n';;
            cout << z << '\n';
        }*/
        tnode* cur = new tnode(x, z);
        cur = merge(split1.f, cur);
      /*  if (z == -4){
            cout << cur->sum << '\n';
        }*/
        v = merge(cur, split1.s);
        /*if (z == -4){
            cout << v->sum << '\n';
            cout << v->y << '\n';
        }*/
        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;
/*
 kek
2
1
3 3
aloha
3
4 1
-4
-1
3
1
4 1 2 4
*/
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);
          //  cout << v << " " << l2 << " " << r2 << " " << add << '\n';
            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){
            int kek = tree.get(r, t[v]);
         //   cout << v << " " << kek << '\n';
            return kek;
        }
        int tm = (tl + tr) / 2;
        int add = tree.get(r, t[v]);
       // cout << "sum\n";
       // cout << v << " " << tl << " " << tr << " " << add << '\n';
        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"){
            cin >> x;
            if (s[x] == '0'){
                setik.erase(x);
                auto it = setik.upper_bound(x);
                r = *it;
                l = *(--it) + 1;
                tree2.upd(l, x, x, r, -i);
                s[x] = '1';
            }
            else{
                auto it = setik.upper_bound(x);
                r = *it;
                l = *(--it) + 1;
                setik.insert(x);
                tree2.upd(l, x, x, r, i);
                s[x] = '0';
            }
          //  cout << tree.get(1, tree2.t[4]) << " " << tree.get(2, tree2.t[4]) << " " << tree.get(3, tree2.t[4]) << '\n';
        }
        else{
            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';
        }
    }
}

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