oj.uz

답안 #291298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291298 2020-09-05T05:12:01 Z davooddkareshki 가로등 (APIO19_street_lamps) C++17
20 / 100
 1175 ms 366324 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*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)
{
    /// 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];

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, 1);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 138872 KB Output is correct
2 Correct 86 ms 138932 KB Output is correct
3 Correct 86 ms 138872 KB Output is correct
4 Correct 85 ms 138872 KB Output is correct
5 Correct 86 ms 138872 KB Output is correct
6 Correct 84 ms 139000 KB Output is correct
7 Correct 85 ms 138872 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 149112 KB Output is correct
2 Correct 448 ms 149368 KB Output is correct
3 Correct 822 ms 152124 KB Output is correct
4 Runtime error 1030 ms 349152 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 139000 KB Output is correct
2 Correct 91 ms 139000 KB Output is correct
3 Correct 89 ms 139000 KB Output is correct
4 Correct 84 ms 138872 KB Output is correct
5 Runtime error 1175 ms 366324 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 139000 KB Output is correct
2 Correct 85 ms 139000 KB Output is correct
3 Correct 86 ms 139128 KB Output is correct
4 Correct 88 ms 139084 KB Output is correct
5 Runtime error 681 ms 312536 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 138872 KB Output is correct
2 Correct 86 ms 138932 KB Output is correct
3 Correct 86 ms 138872 KB Output is correct
4 Correct 85 ms 138872 KB Output is correct
5 Correct 86 ms 138872 KB Output is correct
6 Correct 84 ms 139000 KB Output is correct
7 Correct 85 ms 138872 KB Output is correct
8 Correct 380 ms 149112 KB Output is correct
9 Correct 448 ms 149368 KB Output is correct
10 Correct 822 ms 152124 KB Output is correct
11 Runtime error 1030 ms 349152 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -