oj.uz

Submission #1005594

# Submission time Handle Problem Language Result Execution time Memory
1005594 2024-06-22T15:59:07 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2123 ms 143888 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int mxn=3e5+5;
int a[mxn],b[mxn],ans[mxn],n;
bool vis[mxn]{0};
vector<pii>qr[mxn];
multiset<int>ms,ms2;
vector<int>bit[mxn];
vector<int>bval[mxn];
vector<int>val[mxn];
void build(){
    for(int i=1;i<=n;i++){
        if(val[i].empty())continue;
        sort(val[i].begin(),val[i].end());
        for(auto it : val[i]){
            for(int j=i;j<=n;j+=j&-j){
                bval[j].pb(it);
            }
        }
    }
    for(int i=1;i<=n;i++)sort(bval[i].begin(),bval[i].end()),bval[i].erase(unique(bval[i].begin(),bval[i].end()),bval[i].end());
    for(int i=1;i<=n;i++)bit[i].resize((int)bval[i].size()+1,0);
}
int ub(int x,int y){
    return upper_bound(bval[x].begin(),bval[x].end(),y)-bval[x].begin();
}
void upd(int i,int j,int amt){
    for(int x=i;x<=n;x+=x&-x)for(int y=ub(x,j);y<bit[x].size();y+=y&-y)bit[x][y]+=amt;
}
int query(int a,int b,int res=0){
    for(int x=a;x>0;x-=x&-x)for(int y=ub(x,b);y>0;y-=y&-y)res+=bit[x][y];
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int q;cin>>n>>q;ms.insert(0);ms.insert(n+1);ms2.insert(0);ms2.insert(n+1);
    for(int i=1;i<=n;i++){
        char x;cin>>x;a[i]=x-'0';b[i]=a[i];
        if(!a[i])ms.insert(i),ms2.insert(i);
    }vector<pair<int,pii>>qq;
    for(int i=1;i<=q;i++){
        string s;cin>>s;ans[i]=-1;
        if(s=="toggle"){
            int x;cin>>x;qq.pb({1,{x,0}});
            if(a[x]){
                int l = 1+*prev(ms.lower_bound(x));
                int r = -1+*ms.upper_bound(x);
                val[l].pb(x);val[l].pb(r+1);val[x+1].pb(x);val[x+1].pb(r+1);
                a[x]=0;ms.insert(x);
            }
            else {
                int l = 1+*prev(ms.lower_bound(x));
                int r = -1+*ms.upper_bound(x);
                val[l].pb(x);val[l].pb(r+1);val[x+1].pb(x);val[x+1].pb(r+1);
                a[x]=1;ms.erase(x);
             }
        }
        else {
            int l,r;cin>>l>>r;qq.pb({2,{l,r}});
        }
    }build();
    for(int i=0;i<qq.size();i++){
        auto it=qq[i];
        if(it.f==1){int x=it.s.f;
            if(b[x]){
                int l = 1+*prev(ms2.lower_bound(x));
                int r = -1+*ms2.upper_bound(x);
                upd(l,x,i+1);upd(l,r+1,-i-1);upd(x+1,x,-i-1);upd(x+1,r+1,i+1);
                b[x]=0;ms2.insert(x);
            }
            else {
                int l = 1+*prev(ms2.lower_bound(x));
                int r = -1+*ms2.upper_bound(x);
                upd(l,x,-i-1);upd(l,r+1,i+1);upd(x+1,x,i+1);upd(x+1,r+1,-i-1);
                b[x]=1;ms2.erase(x);
            }
        }
        else {
            ans[i+1] = query(it.s.f,it.s.s-1);
            int ij = *ms2.lower_bound(it.s.f);
            if(ij>it.s.s-1)ans[i+1]+=i+1;
        }
    }
    for(int i=1;i<=q;i++)if(ans[i]!=-1)cout<<ans[i]<<'\n';
}

Compilation message

street_lamps.cpp: In function 'void upd(int, int, int)':
street_lamps.cpp:40:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int x=i;x<=n;x+=x&-x)for(int y=ub(x,j);y<bit[x].size();y+=y&-y)bit[x][y]+=amt;
      |                                                ~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<qq.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 6 ms 31192 KB Output is correct
3 Correct 5 ms 31196 KB Output is correct
4 Correct 5 ms 31320 KB Output is correct
5 Correct 5 ms 31360 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 54004 KB Output is correct
2 Correct 247 ms 53820 KB Output is correct
3 Correct 428 ms 61452 KB Output is correct
4 Correct 1052 ms 106484 KB Output is correct
5 Correct 925 ms 89928 KB Output is correct
6 Correct 1234 ms 116952 KB Output is correct
7 Correct 321 ms 79088 KB Output is correct
8 Correct 81 ms 51892 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31580 KB Output is correct
2 Correct 7 ms 31624 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 2123 ms 143888 KB Output is correct
6 Correct 1500 ms 119544 KB Output is correct
7 Correct 969 ms 90328 KB Output is correct
8 Correct 115 ms 51892 KB Output is correct
9 Correct 81 ms 36544 KB Output is correct
10 Correct 91 ms 40584 KB Output is correct
11 Correct 85 ms 39868 KB Output is correct
12 Correct 334 ms 78332 KB Output is correct
13 Correct 101 ms 52008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31320 KB Output is correct
2 Correct 6 ms 31580 KB Output is correct
3 Correct 7 ms 31448 KB Output is correct
4 Correct 7 ms 31580 KB Output is correct
5 Correct 285 ms 67600 KB Output is correct
6 Correct 821 ms 93724 KB Output is correct
7 Correct 1347 ms 116708 KB Output is correct
8 Correct 1947 ms 141048 KB Output is correct
9 Correct 274 ms 68520 KB Output is correct
10 Correct 265 ms 67064 KB Output is correct
11 Correct 309 ms 69364 KB Output is correct
12 Correct 239 ms 67064 KB Output is correct
13 Correct 298 ms 67832 KB Output is correct
14 Correct 326 ms 67304 KB Output is correct
15 Correct 319 ms 80372 KB Output is correct
16 Correct 122 ms 53796 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 6 ms 31192 KB Output is correct
3 Correct 5 ms 31196 KB Output is correct
4 Correct 5 ms 31320 KB Output is correct
5 Correct 5 ms 31360 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 256 ms 54004 KB Output is correct
9 Correct 247 ms 53820 KB Output is correct
10 Correct 428 ms 61452 KB Output is correct
11 Correct 1052 ms 106484 KB Output is correct
12 Correct 925 ms 89928 KB Output is correct
13 Correct 1234 ms 116952 KB Output is correct
14 Correct 321 ms 79088 KB Output is correct
15 Correct 81 ms 51892 KB Output is correct
16 Correct 7 ms 31580 KB Output is correct
17 Correct 7 ms 31624 KB Output is correct
18 Correct 5 ms 31324 KB Output is correct
19 Correct 4 ms 31324 KB Output is correct
20 Correct 2123 ms 143888 KB Output is correct
21 Correct 1500 ms 119544 KB Output is correct
22 Correct 969 ms 90328 KB Output is correct
23 Correct 115 ms 51892 KB Output is correct
24 Correct 81 ms 36544 KB Output is correct
25 Correct 91 ms 40584 KB Output is correct
26 Correct 85 ms 39868 KB Output is correct
27 Correct 334 ms 78332 KB Output is correct
28 Correct 101 ms 52008 KB Output is correct
29 Correct 6 ms 31320 KB Output is correct
30 Correct 6 ms 31580 KB Output is correct
31 Correct 7 ms 31448 KB Output is correct
32 Correct 7 ms 31580 KB Output is correct
33 Correct 285 ms 67600 KB Output is correct
34 Correct 821 ms 93724 KB Output is correct
35 Correct 1347 ms 116708 KB Output is correct
36 Correct 1947 ms 141048 KB Output is correct
37 Correct 274 ms 68520 KB Output is correct
38 Correct 265 ms 67064 KB Output is correct
39 Correct 309 ms 69364 KB Output is correct
40 Correct 239 ms 67064 KB Output is correct
41 Correct 298 ms 67832 KB Output is correct
42 Correct 326 ms 67304 KB Output is correct
43 Correct 319 ms 80372 KB Output is correct
44 Correct 122 ms 53796 KB Output is correct
45 Correct 77 ms 43776 KB Output is correct
46 Correct 151 ms 44544 KB Output is correct
47 Correct 530 ms 69116 KB Output is correct
48 Correct 1151 ms 110288 KB Output is correct
49 Correct 60 ms 42436 KB Output is correct
50 Correct 57 ms 41152 KB Output is correct
51 Correct 61 ms 41928 KB Output is correct
52 Correct 67 ms 41920 KB Output is correct
53 Correct 58 ms 42440 KB Output is correct
54 Correct 93 ms 41668 KB Output is correct