oj.uz

Submission #291288

# Submission time Handle Problem Language Result Execution time Memory
291288 2020-09-05T04:59:49 Z davooddkareshki Street Lamps (APIO19_street_lamps) C++17
20 / 100
 2673 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 = 3e5+10;
const int mod = 1e9+7;
const int inf = 1e9+10;

int n, q;

struct paralel_segment
{
    int root[maxn<<2], seg[maxn*80], lst, L[maxn*80], R[maxn*80];
    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 183 ms 350304 KB Output is correct
2 Correct 185 ms 350332 KB Output is correct
3 Correct 184 ms 350328 KB Output is correct
4 Correct 185 ms 350228 KB Output is correct
5 Correct 183 ms 350328 KB Output is correct
6 Correct 186 ms 350328 KB Output is correct
7 Correct 180 ms 350200 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 362312 KB Output is correct
2 Correct 545 ms 362620 KB Output is correct
3 Correct 886 ms 365432 KB Output is correct
4 Correct 2600 ms 389448 KB Output is correct
5 Correct 2673 ms 385884 KB Output is correct
6 Runtime error 2601 ms 524288 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 350464 KB Output is correct
2 Correct 201 ms 350332 KB Output is correct
3 Correct 198 ms 350328 KB Output is correct
4 Correct 193 ms 350328 KB Output is correct
5 Runtime error 2672 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 192 ms 350332 KB Output is correct
2 Correct 202 ms 350328 KB Output is correct
3 Correct 197 ms 350328 KB Output is correct
4 Correct 204 ms 350456 KB Output is correct
5 Correct 1116 ms 369760 KB Output is correct
6 Correct 1784 ms 378208 KB Output is correct
7 Runtime error 2546 ms 524288 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 350304 KB Output is correct
2 Correct 185 ms 350332 KB Output is correct
3 Correct 184 ms 350328 KB Output is correct
4 Correct 185 ms 350228 KB Output is correct
5 Correct 183 ms 350328 KB Output is correct
6 Correct 186 ms 350328 KB Output is correct
7 Correct 180 ms 350200 KB Output is correct
8 Correct 469 ms 362312 KB Output is correct
9 Correct 545 ms 362620 KB Output is correct
10 Correct 886 ms 365432 KB Output is correct
11 Correct 2600 ms 389448 KB Output is correct
12 Correct 2673 ms 385884 KB Output is correct
13 Runtime error 2601 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -