oj.uz

Submission #859375

# Submission time Handle Problem Language Result Execution time Memory
859375 2023-10-10T05:49:11 Z winter0101 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1365 ms 89204 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=3e5+9;
vector<int>node[maxn];
vector<long long>bit[maxn];
int n,q;
void fakeupdate(int x,int y){
for(;x<=n;x+=(x-(x&(x-1)))){
node[x].pb(y);
}
}
void fakeget(int x,int y){
for(;x>=1;x-=(x-(x&(x-1)))){
node[x].pb(y);
}
}
void build(){
for1(i,1,n){
sort(all(node[i]));
auto it=unique(all(node[i]));
node[i].resize(distance(node[i].begin(),it));
bit[i].resize(sz(node[i]));
}
}
void update(int x,int y,int val){
for(;x<=n;x+=(x-(x&(x-1)))){
    for(int yy=lower_bound(all(node[x]),y)-node[x].begin();yy<sz(node[x]);yy+=(yy-(yy&(yy-1)))){
    bit[x][yy]+=val;
    }
}
}
long long get(int x,int y){
long long sum=0;
for(;x>=1;x-=(x-(x&(x-1)))){
    for(int yy=lower_bound(all(node[x]),y)-node[x].begin();yy>=1;yy-=(yy-(yy&(yy-1)))){
    sum+=bit[x][yy];
    }
}
return sum;
}
struct line{
int l,r,t;
bool operator <(const line &p)const{
return r<p.r;
}
};
struct query{
int type,x,y;
}b[maxn];
void fakerect(int x1,int y1,int x2,int y2){
fakeget(x1-1,y1-1);
fakeget(x2,y2);
fakeget(x2,y1-1);
fakeget(x1-1,y2);
}
long long getrect(int x1,int y1,int x2,int y2){
return get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    string s;
    cin>>s;
    s=" "+s;
    for1(i,1,n)node[i].pb(0);
    multiset<line>nt;
    for1(i,1,n){
    if (s[i]=='0')continue;
    else {
    int p=i;
    for1(j,i,n){
    if (s[j]!=s[i])break;
    p=j;
    }
    nt.insert({i,p,1});
    i=p;
    }
    }
    string t=s;
    for1(i,1,q){
    //cin>>b[i].type;
    string quest;
    cin>>quest;
    if (quest=="query")b[i].type=1;
    else b[i].type=2;
    if (b[i].type==1){
    cin>>b[i].x>>b[i].y;
    if (b[i].x>b[i].y)swap(b[i].x,b[i].y);
    if (b[i].x==b[i].y)continue;
    b[i].y--;
    //small than x and large than y
    fakerect(1,b[i].y,b[i].x,n);
    }
    else {
    cin>>b[i].x;
    if (s[b[i].x]=='1'){
    s[b[i].x]='0';
    auto it=nt.lower_bound({b[i].x,b[i].x,-1});
    line temp=(*it);
    fakeupdate(temp.l,temp.r);
    nt.erase(it);
    if (temp.l<b[i].x){
    nt.insert({temp.l,b[i].x-1,i});
    }
    if (temp.r>b[i].x){
    nt.insert({b[i].x+1,temp.r,i});
    }
    }
    else {
    s[b[i].x]='1';
    auto it=nt.upper_bound({b[i].x,b[i].x,-1});
    line nw={b[i].x,b[i].x,i};
    if (it!=nt.begin()){
    it--;
    line temp=(*it);
    if (temp.r+1==b[i].x){
    nt.erase(it);
    fakeupdate(temp.l,temp.r);
    nw.l=temp.l;
    }
    }
    it=nt.upper_bound({b[i].x,b[i].x,-1});
    if (it!=nt.end()){
    line temp=(*it);
    if (temp.l==b[i].x+1){
    nt.erase(it);
    fakeupdate(temp.l,temp.r);
    nw.r=temp.r;
    }
    }
    nt.insert(nw);
    }
    }
    }
    build();
    s=t;
    nt.clear();
    for1(i,1,n){
    if (s[i]=='0')continue;
    else {
    int p=i;
    for1(j,i,n){
    if (s[j]!=s[i])break;
    p=j;
    }
    nt.insert({i,p,0});
    i=p;
    }
    }
    for1(i,1,q){
    if (b[i].type==1){
    //cout<<b[i].x<<" "<<b[i].y<<'\n';
    if (b[i].x>b[i].y){
    cout<<i<<'\n';
    continue;
    }
    //small than x and large than y
    long long ans=getrect(1,b[i].y,b[i].x,n);
    auto it=nt.lower_bound({b[i].x,b[i].y,-1});
    if (it!=nt.end()){
    auto temp=(*it);
    if (temp.r>=b[i].y&&temp.l<=b[i].x){
    ans+=i-temp.t;
    //cout<<temp.l<<" "<<temp.r<<" "<<b[i].x<<" "<<b[i].y<<" "<<temp.t<<" "<<ans<<'\n';
    }
    }
    cout<<ans<<'\n';
    }
    else {
    if (s[b[i].x]=='1'){
    s[b[i].x]='0';
    auto it=nt.lower_bound({b[i].x,b[i].x,-1});
    line temp=(*it);
    update(temp.l,temp.r,i-temp.t);
    nt.erase(it);
    if (temp.l<b[i].x){
    nt.insert({temp.l,b[i].x-1,i});
    }
    if (temp.r>b[i].x){
    nt.insert({b[i].x+1,temp.r,i});
    }
    }
    else {
    s[b[i].x]='1';
    auto it=nt.upper_bound({b[i].x,b[i].x,-1});
    line nw={b[i].x,b[i].x,i};
    if (it!=nt.begin()){
    it--;
    line temp=(*it);
    if (temp.r+1==b[i].x){
    nt.erase(it);
    update(temp.l,temp.r,i-temp.t);
    nw.l=temp.l;
    }
    }
    it=nt.upper_bound({b[i].x,b[i].x,-1});
    if (it!=nt.end()){
    line temp=(*it);
    if (temp.l==b[i].x+1){
    nt.erase(it);
    update(temp.l,temp.r,i-temp.t);
    nw.r=temp.r;
    }
    }
    nt.insert(nw);
    }
    }
    }



}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15852 KB Output is correct
4 Correct 4 ms 15716 KB Output is correct
5 Correct 4 ms 15704 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 29640 KB Output is correct
2 Correct 216 ms 30332 KB Output is correct
3 Correct 388 ms 36028 KB Output is correct
4 Correct 1310 ms 78644 KB Output is correct
5 Correct 1365 ms 85344 KB Output is correct
6 Correct 1201 ms 77696 KB Output is correct
7 Correct 911 ms 79560 KB Output is correct
8 Correct 928 ms 80984 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15960 KB Output is correct
2 Correct 6 ms 15800 KB Output is correct
3 Correct 5 ms 15812 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 1168 ms 71456 KB Output is correct
6 Correct 1346 ms 81116 KB Output is correct
7 Correct 1337 ms 88756 KB Output is correct
8 Correct 924 ms 85680 KB Output is correct
9 Correct 122 ms 27704 KB Output is correct
10 Correct 131 ms 28480 KB Output is correct
11 Correct 140 ms 28728 KB Output is correct
12 Correct 922 ms 84488 KB Output is correct
13 Correct 917 ms 85612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15960 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 5 ms 15860 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 1110 ms 89204 KB Output is correct
6 Correct 1104 ms 84656 KB Output is correct
7 Correct 1152 ms 78040 KB Output is correct
8 Correct 1253 ms 69416 KB Output is correct
9 Correct 237 ms 29200 KB Output is correct
10 Correct 174 ms 25132 KB Output is correct
11 Correct 234 ms 28952 KB Output is correct
12 Correct 177 ms 25132 KB Output is correct
13 Correct 241 ms 29140 KB Output is correct
14 Correct 177 ms 25280 KB Output is correct
15 Correct 968 ms 84436 KB Output is correct
16 Correct 1012 ms 85700 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15852 KB Output is correct
4 Correct 4 ms 15716 KB Output is correct
5 Correct 4 ms 15704 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 184 ms 29640 KB Output is correct
9 Correct 216 ms 30332 KB Output is correct
10 Correct 388 ms 36028 KB Output is correct
11 Correct 1310 ms 78644 KB Output is correct
12 Correct 1365 ms 85344 KB Output is correct
13 Correct 1201 ms 77696 KB Output is correct
14 Correct 911 ms 79560 KB Output is correct
15 Correct 928 ms 80984 KB Output is correct
16 Correct 5 ms 15960 KB Output is correct
17 Correct 6 ms 15800 KB Output is correct
18 Correct 5 ms 15812 KB Output is correct
19 Correct 4 ms 15964 KB Output is correct
20 Correct 1168 ms 71456 KB Output is correct
21 Correct 1346 ms 81116 KB Output is correct
22 Correct 1337 ms 88756 KB Output is correct
23 Correct 924 ms 85680 KB Output is correct
24 Correct 122 ms 27704 KB Output is correct
25 Correct 131 ms 28480 KB Output is correct
26 Correct 140 ms 28728 KB Output is correct
27 Correct 922 ms 84488 KB Output is correct
28 Correct 917 ms 85612 KB Output is correct
29 Correct 4 ms 15960 KB Output is correct
30 Correct 4 ms 15964 KB Output is correct
31 Correct 5 ms 15860 KB Output is correct
32 Correct 4 ms 15964 KB Output is correct
33 Correct 1110 ms 89204 KB Output is correct
34 Correct 1104 ms 84656 KB Output is correct
35 Correct 1152 ms 78040 KB Output is correct
36 Correct 1253 ms 69416 KB Output is correct
37 Correct 237 ms 29200 KB Output is correct
38 Correct 174 ms 25132 KB Output is correct
39 Correct 234 ms 28952 KB Output is correct
40 Correct 177 ms 25132 KB Output is correct
41 Correct 241 ms 29140 KB Output is correct
42 Correct 177 ms 25280 KB Output is correct
43 Correct 968 ms 84436 KB Output is correct
44 Correct 1012 ms 85700 KB Output is correct
45 Correct 87 ms 22476 KB Output is correct
46 Correct 130 ms 24440 KB Output is correct
47 Correct 628 ms 49692 KB Output is correct
48 Correct 1263 ms 80460 KB Output is correct
49 Correct 154 ms 29440 KB Output is correct
50 Correct 148 ms 29420 KB Output is correct
51 Correct 157 ms 30004 KB Output is correct
52 Correct 196 ms 33076 KB Output is correct
53 Correct 197 ms 33080 KB Output is correct
54 Correct 200 ms 33084 KB Output is correct