oj.uz

Submission #477634

# Submission time Handle Problem Language Result Execution time Memory
477634 2021-10-02T23:09:20 Z RGBB Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2795 ms 120200 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pi;
const int MAX=3*1e5;
//input
int n,q,state[MAX],inp[MAX][2];
bool type[MAX];//true is toggle, false is query
string s;
//first sweep
int beg[MAX];
map<int,int>lines;
vector<pi>add[MAX],sub[MAX];//location, value
void firstSweep(){
    int orig=0;
    for(int i=0;i<n;i++){
        if(state[i]==1){
            if(i!=0&&state[i-1]==1)lines[orig]++;
            else{
                lines[i]=i;
                orig=i;
            }
        }
        else beg[i]=i-1;
    }
    for(auto&[i,j]:lines)for(int k=i;k<=j;k++)beg[k]=j;
    for(int i=0;i<q-1;i++){
        if(!type[i])continue;
        int cur=inp[i][0];
        if(state[cur]==1){
            state[cur]=0;
            pi cl=*prev(lines.upper_bound(cur));
            lines.erase(lines.find(cl.first));
            if(cur!=cl.first)lines[cl.first]=cur-1;
            if(cur!=cl.second)lines[cur+1]=cl.second;
            add[cl.first].push_back({i+1,cur-1});
            sub[cur].push_back({i+1,cur-1});
        }
        else{
            state[cur]=1;
            int lef=cur;
            int rig=cur;
            if(lines.find(cur+1)!=lines.end()){
                rig=lines[cur+1];
                lines.erase(lines.find(cur+1));
            }
            if(lines.upper_bound(cur)!=lines.begin()){
                pi cl=*prev(lines.upper_bound(cur));
                if(cl.second==cur-1){
                    lef=cl.first;
                    lines.erase(lines.find(cl.first));
                }
            }
            lines[lef]=rig;
            add[lef].push_back({i+1,rig});
            sub[cur].push_back({i+1,rig});
        }
    }
}
//second sweep
struct sparseBIT{
    vector<pi>todo;
    int cnt[MAX+1],st[MAX+1];
    vector<int>val,bit;
    void init(){
        int lst[MAX+1];
        for(int i=0;i<=MAX;i++)lst[i]=cnt[i]=0;
        sort(todo.begin(),todo.end(),[](const pi&a,const pi&b){return a.second<b.second;});
        for(pi t:todo){
            for(int x=t.first;x<=MAX;x+=x&-x){
                if(lst[x]!=t.second){
                    lst[x]=t.second;
                    cnt[x]++;
                }
            }
        }
        int sum=0;
        for(int i=0;i<=MAX;i++){
            lst[i]=0;
            st[i]=sum;
            sum+=cnt[i];
        }
        val.resize(sum);
        bit.resize(sum);
        for(pi t:todo){
            for(int x=t.first;x<=MAX;x+=x&-x){
                if(lst[x]!=t.second){
                    lst[x]=t.second;
                    val[st[x]++]=t.second;
                }
            }
        }
    }
    void push(int x,int y){
        if(x<0||x>=MAX||y<0||y>=MAX)return;
        todo.push_back({x+1,y+1});
    }
    int rank(int y,int l,int r){return upper_bound(begin(val)+l,begin(val)+r,y)-begin(val)-l;}
    void UPDATE(int x,int y,int t){
        int z=st[x]-cnt[x];
        for(y=rank(y,z,st[x]);y<=cnt[x];y+=y&-y)bit[z+y-1]+=t;
    }
    void update(int x,int y,int t){
        if(x<0||x>=MAX||y<0||y>=MAX)return;
        x++;
        y++;
        for(;x<=MAX;x+=x&-x)UPDATE(x,y,t);
    }
    int QUERY(int x,int y){
        int ret=0;
        int z=st[x]-cnt[x];
        for(y=rank(y,z,st[x]);y;y-=y&-y)ret+=bit[z+y-1];
        return ret;
    }
    int query(int x,int y){
        if(x<0||x>=MAX||y<0||y>=MAX)return 0;
        x++;
        y++;
        int ret=0;
        for(;x;x-=x&-x)ret+=QUERY(x,y);
        return ret;
    }
};
int val[MAX],outp[MAX];
vector<pi>query[MAX];
set<int>nei;
sparseBIT bit;
void processInsert(int p,int v){
    nei.insert(p);
    val[p]=v;
    int nxt=*next(nei.find(p));
    bit.update(p,MAX-1-v,nxt-p);
    if(p!=0){
        int prv=*prev(nei.find(p));
        bit.update(prv,MAX-1-val[prv],p-nxt);
    }
}
void processDelete(int p,int v){
    int nxt=*next(nei.find(p));
    bit.update(p,MAX-1-v,p-nxt);
    if(p!=0){
        int prv=*prev(nei.find(p));
        bit.update(prv,MAX-1-val[prv],nxt-p);
    }
    nei.erase(nei.find(p));
}
int processQuery(int p,int v){
    int prv=*prev(nei.upper_bound(p));
    int ret=bit.query(prv-1,MAX-1-v);
    if(val[prv]>=v)ret+=p-prv+1;
    return ret;
}
void secondSweep(){
    nei.insert(q);
    for(int i=0;i<n;i++)bit.push(0,MAX-1-beg[i]);
    for(int i=0;i<n;i++)for(pi j:add[i])bit.push(j.first,MAX-1-j.second);
    bit.init();
    for(int i=0;i<n;i++){
        processInsert(0,beg[i]);
        for(pi j:add[i])processInsert(j.first,j.second);
        for(pi j:query[i])outp[j.first]=processQuery(j.first,j.second);
        for(pi j:sub[i])processDelete(j.first,j.second);
        processDelete(0,beg[i]);
    }
}
//driver
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>q>>s;
    for(int i=0;i<n;i++)state[i]=s[i]-'0';
    for(int i=0;i<q;i++){
        string op;
        cin>>op;
        if(op=="toggle"){
            type[i]=true;
            cin>>inp[i][0];
            inp[i][0]--;
        }
        else{
            type[i]=false;
            cin>>inp[i][0]>>inp[i][1];
            inp[i][0]--;
            inp[i][1]-=2;
        }
    }
    firstSweep();
    for(int i=0;i<q;i++)if(!type[i])query[inp[i][0]].push_back({i,inp[i][1]});
    secondSweep();
    for(int i=0;i<q;i++)if(!type[i])cout<<outp[i]<<"\n";
}

Compilation message

street_lamps.cpp: In function 'void firstSweep()':
street_lamps.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto&[i,j]:lines)for(int k=i;k<=j;k++)beg[k]=j;
      |              ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24912 KB Output is correct
2 Correct 13 ms 24940 KB Output is correct
3 Correct 13 ms 25028 KB Output is correct
4 Correct 13 ms 24932 KB Output is correct
5 Correct 13 ms 24928 KB Output is correct
6 Correct 13 ms 24912 KB Output is correct
7 Correct 12 ms 24912 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 45772 KB Output is correct
2 Correct 550 ms 47000 KB Output is correct
3 Correct 794 ms 50748 KB Output is correct
4 Correct 2118 ms 88896 KB Output is correct
5 Correct 1389 ms 78792 KB Output is correct
6 Correct 2215 ms 90648 KB Output is correct
7 Correct 834 ms 91564 KB Output is correct
8 Correct 345 ms 48272 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 25296 KB Output is correct
2 Correct 20 ms 25164 KB Output is correct
3 Correct 17 ms 25080 KB Output is correct
4 Correct 14 ms 25080 KB Output is correct
5 Correct 2447 ms 120200 KB Output is correct
6 Correct 1960 ms 99544 KB Output is correct
7 Correct 1411 ms 77816 KB Output is correct
8 Correct 335 ms 47864 KB Output is correct
9 Correct 102 ms 34520 KB Output is correct
10 Correct 103 ms 35420 KB Output is correct
11 Correct 107 ms 35296 KB Output is correct
12 Correct 828 ms 91192 KB Output is correct
13 Correct 340 ms 47876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25168 KB Output is correct
2 Correct 16 ms 25200 KB Output is correct
3 Correct 17 ms 25220 KB Output is correct
4 Correct 18 ms 25260 KB Output is correct
5 Correct 994 ms 72680 KB Output is correct
6 Correct 1738 ms 81956 KB Output is correct
7 Correct 2261 ms 89924 KB Output is correct
8 Correct 2795 ms 98372 KB Output is correct
9 Correct 721 ms 49928 KB Output is correct
10 Correct 740 ms 49888 KB Output is correct
11 Correct 699 ms 49892 KB Output is correct
12 Correct 715 ms 49632 KB Output is correct
13 Correct 675 ms 49816 KB Output is correct
14 Correct 689 ms 49708 KB Output is correct
15 Correct 812 ms 91168 KB Output is correct
16 Correct 358 ms 47896 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24912 KB Output is correct
2 Correct 13 ms 24940 KB Output is correct
3 Correct 13 ms 25028 KB Output is correct
4 Correct 13 ms 24932 KB Output is correct
5 Correct 13 ms 24928 KB Output is correct
6 Correct 13 ms 24912 KB Output is correct
7 Correct 12 ms 24912 KB Output is correct
8 Correct 470 ms 45772 KB Output is correct
9 Correct 550 ms 47000 KB Output is correct
10 Correct 794 ms 50748 KB Output is correct
11 Correct 2118 ms 88896 KB Output is correct
12 Correct 1389 ms 78792 KB Output is correct
13 Correct 2215 ms 90648 KB Output is correct
14 Correct 834 ms 91564 KB Output is correct
15 Correct 345 ms 48272 KB Output is correct
16 Correct 18 ms 25296 KB Output is correct
17 Correct 20 ms 25164 KB Output is correct
18 Correct 17 ms 25080 KB Output is correct
19 Correct 14 ms 25080 KB Output is correct
20 Correct 2447 ms 120200 KB Output is correct
21 Correct 1960 ms 99544 KB Output is correct
22 Correct 1411 ms 77816 KB Output is correct
23 Correct 335 ms 47864 KB Output is correct
24 Correct 102 ms 34520 KB Output is correct
25 Correct 103 ms 35420 KB Output is correct
26 Correct 107 ms 35296 KB Output is correct
27 Correct 828 ms 91192 KB Output is correct
28 Correct 340 ms 47876 KB Output is correct
29 Correct 14 ms 25168 KB Output is correct
30 Correct 16 ms 25200 KB Output is correct
31 Correct 17 ms 25220 KB Output is correct
32 Correct 18 ms 25260 KB Output is correct
33 Correct 994 ms 72680 KB Output is correct
34 Correct 1738 ms 81956 KB Output is correct
35 Correct 2261 ms 89924 KB Output is correct
36 Correct 2795 ms 98372 KB Output is correct
37 Correct 721 ms 49928 KB Output is correct
38 Correct 740 ms 49888 KB Output is correct
39 Correct 699 ms 49892 KB Output is correct
40 Correct 715 ms 49632 KB Output is correct
41 Correct 675 ms 49816 KB Output is correct
42 Correct 689 ms 49708 KB Output is correct
43 Correct 812 ms 91168 KB Output is correct
44 Correct 358 ms 47896 KB Output is correct
45 Correct 219 ms 37432 KB Output is correct
46 Correct 312 ms 38156 KB Output is correct
47 Correct 969 ms 55504 KB Output is correct
48 Correct 2049 ms 88392 KB Output is correct
49 Correct 130 ms 36296 KB Output is correct
50 Correct 124 ms 36260 KB Output is correct
51 Correct 128 ms 36432 KB Output is correct
52 Correct 118 ms 36872 KB Output is correct
53 Correct 117 ms 36848 KB Output is correct
54 Correct 120 ms 36924 KB Output is correct