oj.uz

Submission #756115

# Submission time Handle Problem Language Result Execution time Memory
756115 2023-06-11T06:46:51 Z boyliguanhan Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4062 ms 179024 KB 
#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
int n,N,T,root[600001],cnt;
struct node{
	int l,r,sum;
}seg[15020001];
#define mid ((lb+rb)>>1)
void Update(int &rt,int lb,int rb,int pos,int w){
	if (!rt) rt=++cnt;seg[rt].sum+=w;
	if (lb==rb) return;
	(mid>=pos?Update(seg[rt].l,lb,mid,pos,w):Update(seg[rt].r,mid+1,rb,pos,w));
}
int Query(int rt,int lb,int rb,int l,int r){
	if (!rt||lb>r||rb<l) return 0;
	if (lb>=l&&rb<=r) return seg[rt].sum;
	return Query(seg[rt].l,lb,mid,l,r)+Query(seg[rt].r,mid+1,rb,l,r);
}
inline void update(int pos,int r,int w){
	for (;pos<=n+1;pos+=pos&-pos) Update(root[pos],1,n+1,r,w);
}
inline int query(int posx,int posy){
	int ans=0;
	for (;posx;posx-=posx&-posx) ans+=Query(root[posx],1,n+1,1,posy);
	return ans;
}
inline void Add(int x1,int y1,int x2,int y2,int W){
	update(x1,y1,W);update(x1,y2+1,-W);
	update(x2+1,y1,-W);update(x2+1,y2+1,W);
}
struct road{
	int l,r;
};
inline bool operator < (road a,road b){
	return a.r<b.r;
} 
set<road> S;
set<road>::iterator it;
bool zt[2000001];
signed main(){
	n=1+read(),T=read();N=n-1;
	for (int i=1;i<=n;i++){
		S.insert((road){i,i});
	}
	for (int i=1;i<=N;i++){
		char ch=gc();
		while (!isdigit(ch)) ch=gc();
		zt[i]=(ch-48);
		if (zt[i]){
			it=S.lower_bound((road){0,i+1});it--;
			int lb=(*it).l;
			S.erase(it);S.erase((road){i+1,i+1});
			S.insert((road){lb,i+1});
		}
	}
	for (it=S.begin();it!=S.end();++it){
		Add((*it).l,(*it).l,(*it).r,(*it).r,T);
	}
	for (int t=1;t<=T;t++){
		char s[11];scanf("%s",s+1);
		if (s[1]=='q'){
			int x=read(),y=read();
			int ans=query(x,y);
			int X=(*(S.lower_bound((road){0,x}))).l;
			int Y=(*(S.lower_bound((road){0,y}))).l;
			printf("%d\n",ans-(T-t)*(X==Y));
		}else if (s[1]=='t'){
			int x=read();
			if (zt[x]==1){
				it=S.lower_bound((road){0,x});
				int lb1=(*it).l,rb1=x;
				int lb2=x+1,rb2=(*it).r;
				Add(lb1,lb2,rb1,rb2,t-T);
				S.erase((road){lb1,rb2});
				S.insert((road){lb1,rb1});S.insert((road){lb2,rb2}); 
				zt[x]^=1;
			}else{
				it=S.lower_bound((road){0,x});
				int lb1=(*it).l,rb1=x;
				it++;
				int lb2=x+1,rb2=(*it).r;
				Add(lb1,lb2,rb1,rb2,T-t);
				S.erase((road){lb1,rb1});S.erase((road){lb2,rb2});
				S.insert((road){lb1,rb2}); 
				zt[x]^=1;
			}
		}
	}
    return 0;
}

Compilation message

street_lamps.cpp: In function 'long long int read()':
street_lamps.cpp:7:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 |     register ll x=0,f=1;char ch=gc();
      |                 ^
street_lamps.cpp:7:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 |     register ll x=0,f=1;char ch=gc();
      |                     ^
street_lamps.cpp: In function 'void Update(int&, int, int, int, int)':
street_lamps.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |  if (!rt) rt=++cnt;seg[rt].sum+=w;
      |  ^~
street_lamps.cpp:18:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |  if (!rt) rt=++cnt;seg[rt].sum+=w;
      |                    ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   char s[11];scanf("%s",s+1);
      |              ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 1180 KB Output is correct
2 Correct 320 ms 1644 KB Output is correct
3 Correct 676 ms 4360 KB Output is correct
4 Correct 2680 ms 141680 KB Output is correct
5 Correct 2315 ms 118944 KB Output is correct
6 Correct 2963 ms 145080 KB Output is correct
7 Correct 2582 ms 160464 KB Output is correct
8 Correct 230 ms 16896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 684 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4062 ms 179024 KB Output is correct
6 Correct 3153 ms 154116 KB Output is correct
7 Correct 2048 ms 118356 KB Output is correct
8 Correct 241 ms 16884 KB Output is correct
9 Correct 64 ms 1384 KB Output is correct
10 Correct 76 ms 1352 KB Output is correct
11 Correct 71 ms 1468 KB Output is correct
12 Correct 2255 ms 160456 KB Output is correct
13 Correct 221 ms 17072 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 1482 ms 117536 KB Output is correct
6 Correct 2067 ms 133540 KB Output is correct
7 Correct 2713 ms 144784 KB Output is correct
8 Correct 3422 ms 154920 KB Output is correct
9 Correct 392 ms 916 KB Output is correct
10 Correct 342 ms 612 KB Output is correct
11 Correct 408 ms 836 KB Output is correct
12 Correct 336 ms 612 KB Output is correct
13 Correct 417 ms 1104 KB Output is correct
14 Correct 353 ms 608 KB Output is correct
15 Correct 2206 ms 160456 KB Output is correct
16 Correct 235 ms 16944 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 260 ms 1180 KB Output is correct
9 Correct 320 ms 1644 KB Output is correct
10 Correct 676 ms 4360 KB Output is correct
11 Correct 2680 ms 141680 KB Output is correct
12 Correct 2315 ms 118944 KB Output is correct
13 Correct 2963 ms 145080 KB Output is correct
14 Correct 2582 ms 160464 KB Output is correct
15 Correct 230 ms 16896 KB Output is correct
16 Correct 4 ms 684 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 556 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 4062 ms 179024 KB Output is correct
21 Correct 3153 ms 154116 KB Output is correct
22 Correct 2048 ms 118356 KB Output is correct
23 Correct 241 ms 16884 KB Output is correct
24 Correct 64 ms 1384 KB Output is correct
25 Correct 76 ms 1352 KB Output is correct
26 Correct 71 ms 1468 KB Output is correct
27 Correct 2255 ms 160456 KB Output is correct
28 Correct 221 ms 17072 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 3 ms 596 KB Output is correct
31 Correct 3 ms 596 KB Output is correct
32 Correct 4 ms 596 KB Output is correct
33 Correct 1482 ms 117536 KB Output is correct
34 Correct 2067 ms 133540 KB Output is correct
35 Correct 2713 ms 144784 KB Output is correct
36 Correct 3422 ms 154920 KB Output is correct
37 Correct 392 ms 916 KB Output is correct
38 Correct 342 ms 612 KB Output is correct
39 Correct 408 ms 836 KB Output is correct
40 Correct 336 ms 612 KB Output is correct
41 Correct 417 ms 1104 KB Output is correct
42 Correct 353 ms 608 KB Output is correct
43 Correct 2206 ms 160456 KB Output is correct
44 Correct 235 ms 16944 KB Output is correct
45 Correct 83 ms 1056 KB Output is correct
46 Correct 153 ms 800 KB Output is correct
47 Correct 1091 ms 48664 KB Output is correct
48 Correct 2453 ms 141640 KB Output is correct
49 Correct 77 ms 1100 KB Output is correct
50 Correct 79 ms 1160 KB Output is correct
51 Correct 77 ms 1228 KB Output is correct
52 Correct 87 ms 1232 KB Output is correct
53 Correct 97 ms 1232 KB Output is correct
54 Correct 82 ms 1216 KB Output is correct