oj.uz

Submission #291294

# Submission time Handle Problem Language Result Execution time Memory
291294 2020-09-05T05:07:57 Z davooddkareshki Street Lamps (APIO19_street_lamps) C++17
20 / 100
 2540 ms 524288 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 = 1e6+10;
const int mod = 1e9+7;
const int inf = 1e9+10;

int n, q;

struct paralel_segment
{
    int root[maxn<<2], seg[maxn*20], lst, L[maxn*20], R[maxn*20];
    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(!L[v]) L[v] = ++lst;
        if(!R[v]) R[v] = ++lst;
        if(pos <= tm) add(pos, val, L[v], tl, tm);
        else          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, int tp, int v = 1, int tl = 0, int tr = n)
    {
        if(!seg2.root[v]) seg2.root[v] = ++seg2.lst;
        if(tp == 1)
            seg2.add(val, I, seg2.root[v]);
        else
            seg2.add(val,-I, seg2.root[v]);

        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos, val, I, tp, v<<1, tl, tm);
        else          upd(pos, val, I, tp, 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(!seg2.root[v]) seg2.root[v] = ++seg2.lst;

        if(l > r) return 0;
        if(tl == l && tr == r)
            return seg2.ask(val, n, seg2.root[v]);

        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<<2];
void add(int l, int r, int L, int R, int I, int v = 1, int tl = 0, int tr = q)
{
    /// l, r baezye zamani
    /// L, R bazeye makani

    vec[l].push_back({{L,R},I});
    /*if(v == 1)
    {
     //   rec.push_back({{l,r},{L,R}});
        r = q;
    }*/
/*
    if(l > r) return;
    if(tl == l && tr == r)
    {
        vec[v].push_back({{L,R},I});
        //cout<< I <<" "<< l <<" "<< r <<" "<< L <<" "<< R <<"\n";
        return;
    }

    int tm = (tl + tr) >> 1;
    add(l, min(tm,r), L, R, I, v<<1, tl, tm);
    add(max(tm+1,l), r, L, R, I, v<<1|1, tm+1, tr);*/
}

pii Q[maxn];
int ans[maxn];
void dfs(int v = 1, int tl = 0, int tr = q)
{

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

    if(tl < tr)
    {
        int tm = (tl + tr) >> 1;
        dfs(v<<1, tl, tm);
        dfs(v<<1|1, tm+1, tr);
    }
}

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

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();

                      //  cout<< l <<" "<< r <<"\n";
                        add(mp[l][r], i-1, l, r, i-mp[l][r]);
                        mp[l][r] = 0;
                    }
                }
              //  cout<< (*it).F <<" "<< (*it).S <<"\n";

                if(DO)
                {
                    it = it2; int l = (*it).F, r = (*it).S;
                  //  cout<< l <<" "<< r <<"\n";
                    if(pos-1 == r)
                    {
                        L = l;
                       // cout<< l <<" "<< r <<"\n";
                        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;
    }

    dfs();
    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 273 ms 462200 KB Output is correct
2 Correct 275 ms 462328 KB Output is correct
3 Correct 269 ms 462200 KB Output is correct
4 Correct 268 ms 462328 KB Output is correct
5 Correct 266 ms 462328 KB Output is correct
6 Correct 273 ms 462200 KB Output is correct
7 Correct 269 ms 462368 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 472696 KB Output is correct
2 Correct 627 ms 472952 KB Output is correct
3 Correct 1032 ms 475640 KB Output is correct
4 Runtime error 2472 ms 524288 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 462456 KB Output is correct
2 Correct 272 ms 462304 KB Output is correct
3 Correct 271 ms 462328 KB Output is correct
4 Correct 264 ms 462200 KB Output is correct
5 Runtime error 2540 ms 524288 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 462200 KB Output is correct
2 Correct 266 ms 462328 KB Output is correct
3 Correct 267 ms 462456 KB Output is correct
4 Correct 273 ms 462456 KB Output is correct
5 Correct 1188 ms 479712 KB Output is correct
6 Runtime error 2009 ms 524288 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 462200 KB Output is correct
2 Correct 275 ms 462328 KB Output is correct
3 Correct 269 ms 462200 KB Output is correct
4 Correct 268 ms 462328 KB Output is correct
5 Correct 266 ms 462328 KB Output is correct
6 Correct 273 ms 462200 KB Output is correct
7 Correct 269 ms 462368 KB Output is correct
8 Correct 553 ms 472696 KB Output is correct
9 Correct 627 ms 472952 KB Output is correct
10 Correct 1032 ms 475640 KB Output is correct
11 Runtime error 2472 ms 524288 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -