oj.uz

Submission #291317

# Submission time Handle Problem Language Result Execution time Memory
291317 2020-09-05T05:35:54 Z davooddkareshki Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2513 ms 460284 KB 
#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;

const int maxn = 3e5+5;
const int mod = 1e9+7;
const int inf = 1e9+10;

int n, q;

struct paralel_segment
{
    int root[maxn<<2], seg[maxn*100], lst, L[maxn*100], R[maxn*100];
    paralel_segment()
    {
        memset(root, 0, sizeof root);
        memset(seg, 0, sizeof seg);
        memset(L, 0, sizeof L);
        memset(R, 0, sizeof R);
        lst = 0;
    }

    void add(int pos, int val, int v, int tl = 0, int tr = n)
    {
        if(tl == tr)
        {
            seg[v] += val;
            return;
        }

        int tm = (tl + tr) >> 1;
        if(pos <= tm)
        {
            if(!L[v]) L[v] = ++lst;
            add(pos, val, L[v], tl, tm);
        }
        else
        {
            if(!R[v]) R[v] = ++lst;
            add(pos, val, R[v], tm+1, tr);
        }
        seg[v] = seg[L[v]] + seg[R[v]];
    }

    int ask(int l, int r, int v, int tl = 0, int tr = n)
    {
        if(v == 0 || l > r) return 0;
        if(tl == l && tr == r) return seg[v];

        int tm = (tl + tr) >> 1;
        return ask(l, min(tm,r), L[v], tl, tm) +
                ask(max(tm+1,l), r, R[v], tm+1, tr);
    }
} seg2;

struct segment
{
    void upd(int pos, int val, int I)
    {
        for(; pos <= n; pos |= (pos+1))
        {
            if(!seg2.root[pos]) seg2.root[pos] = ++seg2.lst;
            seg2.add(val, I, seg2.root[pos]);
        }
        /*if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos, val, I, v<<1, tl, tm);
        else          upd(pos, val, I, v<<1|1, tm+1, tr);*/
    }

    int ask(int l, int r, int val, int v = 1, int tl = 0, int tr = n)
    {
        /// tedad adad hadeagal val
      //  if(l > r) return 0;
      //  if(tl == l && tr == r)
       //     return seg2.ask(val, n, seg2.root[v]);

        int res = 0;
        for(; r >= 0; r = (r&(r+1))-1)
            res += seg2.ask(val, n, seg2.root[r]);
        return res;
        /*int tm = (tl + tr) >> 1;
        return ask(l, min(tm,r), val, v<<1, tl, tm) +
                ask(max(tm+1,l), r, val, v<<1|1, tm+1, tr);*/
    }
} seg;

vector<pair<pii,int>> vec[maxn];
void add(int l, int r, int L, int R, int I)
{
    /// l, r baezye zamani
    /// L, R bazeye makani
    vec[l].push_back({{L,R},I});
}

pii Q[maxn];
int ans[maxn];

map<int,int> mp[maxn], mp2[maxn];
bool is[maxn];
int lst;
vector<int> must[maxn*3];

signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> q;
    string s; cin>> s; s = "*" + s;
    int Ll = 0, Rr = 0;

    set<pii> se;
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == '1')
        {
            Rr = i;
            is[i] = 1;
        }
        else Ll = i;

        if(s[i] == '1')
        {
            bool sw = 0;
            if(i == n) sw = 1;
            else if(s[i+1] == '0') sw = 1;

            if(sw)
            {
                mp[Ll+1][Rr] = 0;
                se.insert({Ll+1,Rr});
                mp2[Ll+1][Rr] = ++lst;
            }
        }
    }

    for(int i = 1; i <= q; i++)
    {
        string tp; cin>> tp;
        if(tp == "query")
        {
            int l, r; cin>> l >> r; r--;

            auto it = se.upper_bound({l,inf});
            if(it != se.begin())
            {
                it--; int L = (*it).F, R = (*it).S;
                if(r <= R) must[mp2[L][R]].push_back(i);
            }

            Q[i] = {l,r};
        }
        else
        {
            int pos; cin>> pos;
            if(is[pos])
            {
                auto it = se.upper_bound({pos,inf}); it--;

                int l = (*it).F, r = (*it).S;
                se.erase({l,r});
                for(auto id : must[mp2[l][r]])
                    ans[id] -= i-id;
                must[mp2[l][r]].clear();

                add(mp[l][r], i-1, l, r, i-mp[l][r]);
                mp[l][r] = 0;

                if(pos != l)
                {
                    se.insert({l,pos-1});
                    mp2[l][pos-1] = ++lst;
                    mp[l][pos-1] = i;
                }
                if(pos != r)
                {
                    se.insert({pos+1,r});
                    mp2[pos+1][r] = ++lst;
                    mp[pos+1][r] = i;
                }

                is[pos] = 0;
            }
            else
            {
                int L = pos, R = pos;

                auto it = se.upper_bound({pos,inf});
                bool DO = 0;
                auto it2 = it; if(it2 != se.begin()) {it2--; DO = 1;}
                if(it != se.end())
                {
                    int l = (*it).F, r = (*it).S;
                    if(pos+1 == l)
                    {
                        R = r;
                        se.erase({l,r});
                        for(auto id : must[mp2[l][r]])
                            ans[id] -= i-id;
                        must[mp2[l][r]].clear();

                        add(mp[l][r], i-1, l, r, i-mp[l][r]);
                        mp[l][r] = 0;
                    }
                }

                if(DO)
                {
                    it = it2; int l = (*it).F, r = (*it).S;
                    if(pos-1 == r)
                    {
                        L = l;
                        se.erase({l,r});
                        for(auto id : must[mp2[l][r]])
                            ans[id] -= i-id;
                        must[mp2[l][r]].clear();

                        add(mp[l][r], i-1, l, r, i-mp[l][r]);
                        mp[l][r] = 0;
                    }
                }

                se.insert({L,R});
                mp[L][R] = i;
                mp2[L][R] = ++lst;

                is[pos] = 1;
            }
        }
    }

    for(auto X : se)
    {
        int l = X.F, r = X.S;
        for(auto id : must[mp2[l][r]])
            ans[id] -= q+1-id;
        must[mp2[l][r]].clear();

        add(mp[l][r], q, l, r, q+1-mp[l][r]);
        mp[l][r] = 0;
    }

    for(int i = 0; i <= q; i++)
    {
        for(auto X : vec[i])
            seg.upd(X.F.F, X.F.S, X.S);
        if(Q[i].F)
            ans[i] += seg.ask(0, Q[i].F, Q[i].S);
    }
    for(int i = 1; i <= q; i++)
        if(Q[i].F) cout<< ans[i] <<"\n";

}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 413816 KB Output is correct
2 Correct 226 ms 413688 KB Output is correct
3 Correct 233 ms 413644 KB Output is correct
4 Correct 229 ms 413688 KB Output is correct
5 Correct 228 ms 413688 KB Output is correct
6 Correct 232 ms 413688 KB Output is correct
7 Correct 227 ms 413688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 423876 KB Output is correct
2 Correct 530 ms 424312 KB Output is correct
3 Correct 752 ms 426744 KB Output is correct
4 Correct 2050 ms 447844 KB Output is correct
5 Correct 2045 ms 444452 KB Output is correct
6 Correct 2124 ms 453216 KB Output is correct
7 Correct 353 ms 424164 KB Output is correct
8 Correct 372 ms 427356 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 413816 KB Output is correct
2 Correct 228 ms 413816 KB Output is correct
3 Correct 230 ms 413688 KB Output is correct
4 Correct 225 ms 413688 KB Output is correct
5 Correct 2327 ms 455328 KB Output is correct
6 Correct 2150 ms 455736 KB Output is correct
7 Correct 1583 ms 446008 KB Output is correct
8 Correct 370 ms 427356 KB Output is correct
9 Correct 333 ms 420856 KB Output is correct
10 Correct 338 ms 421240 KB Output is correct
11 Correct 331 ms 421752 KB Output is correct
12 Correct 349 ms 424160 KB Output is correct
13 Correct 374 ms 427492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 413688 KB Output is correct
2 Correct 226 ms 413692 KB Output is correct
3 Correct 223 ms 413780 KB Output is correct
4 Correct 226 ms 413820 KB Output is correct
5 Correct 752 ms 430812 KB Output is correct
6 Correct 1326 ms 438920 KB Output is correct
7 Correct 1843 ms 451468 KB Output is correct
8 Correct 2513 ms 460284 KB Output is correct
9 Correct 530 ms 424696 KB Output is correct
10 Correct 486 ms 424884 KB Output is correct
11 Correct 519 ms 424824 KB Output is correct
12 Correct 476 ms 424856 KB Output is correct
13 Correct 514 ms 424824 KB Output is correct
14 Correct 481 ms 424952 KB Output is correct
15 Correct 352 ms 424168 KB Output is correct
16 Correct 377 ms 427484 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 413816 KB Output is correct
2 Correct 226 ms 413688 KB Output is correct
3 Correct 233 ms 413644 KB Output is correct
4 Correct 229 ms 413688 KB Output is correct
5 Correct 228 ms 413688 KB Output is correct
6 Correct 232 ms 413688 KB Output is correct
7 Correct 227 ms 413688 KB Output is correct
8 Correct 467 ms 423876 KB Output is correct
9 Correct 530 ms 424312 KB Output is correct
10 Correct 752 ms 426744 KB Output is correct
11 Correct 2050 ms 447844 KB Output is correct
12 Correct 2045 ms 444452 KB Output is correct
13 Correct 2124 ms 453216 KB Output is correct
14 Correct 353 ms 424164 KB Output is correct
15 Correct 372 ms 427356 KB Output is correct
16 Correct 226 ms 413816 KB Output is correct
17 Correct 228 ms 413816 KB Output is correct
18 Correct 230 ms 413688 KB Output is correct
19 Correct 225 ms 413688 KB Output is correct
20 Correct 2327 ms 455328 KB Output is correct
21 Correct 2150 ms 455736 KB Output is correct
22 Correct 1583 ms 446008 KB Output is correct
23 Correct 370 ms 427356 KB Output is correct
24 Correct 333 ms 420856 KB Output is correct
25 Correct 338 ms 421240 KB Output is correct
26 Correct 331 ms 421752 KB Output is correct
27 Correct 349 ms 424160 KB Output is correct
28 Correct 374 ms 427492 KB Output is correct
29 Correct 224 ms 413688 KB Output is correct
30 Correct 226 ms 413692 KB Output is correct
31 Correct 223 ms 413780 KB Output is correct
32 Correct 226 ms 413820 KB Output is correct
33 Correct 752 ms 430812 KB Output is correct
34 Correct 1326 ms 438920 KB Output is correct
35 Correct 1843 ms 451468 KB Output is correct
36 Correct 2513 ms 460284 KB Output is correct
37 Correct 530 ms 424696 KB Output is correct
38 Correct 486 ms 424884 KB Output is correct
39 Correct 519 ms 424824 KB Output is correct
40 Correct 476 ms 424856 KB Output is correct
41 Correct 514 ms 424824 KB Output is correct
42 Correct 481 ms 424952 KB Output is correct
43 Correct 352 ms 424168 KB Output is correct
44 Correct 377 ms 427484 KB Output is correct
45 Correct 337 ms 421496 KB Output is correct
46 Correct 366 ms 421496 KB Output is correct
47 Correct 920 ms 433508 KB Output is correct
48 Correct 1707 ms 451016 KB Output is correct
49 Correct 335 ms 421368 KB Output is correct
50 Correct 336 ms 421368 KB Output is correct
51 Correct 337 ms 421496 KB Output is correct
52 Correct 361 ms 421752 KB Output is correct
53 Correct 339 ms 421752 KB Output is correct
54 Correct 341 ms 421752 KB Output is correct