oj.uz

Submission #407275

# Submission time Handle Problem Language Result Execution time Memory
407275 2021-05-18T16:59:03 Z anime Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3073 ms 47212 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T,null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

//#define int long long
#define pb push_back
#define pii pair<int,int>
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define endi puts("");
#define ret return
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
const int N = 3e5+5,INF = 1e9+7;
int q[300005],z[300005],xo;
char s[300005];
vector <pair<pii,int>> der[1200005];

void update(int v,int l,int r,int ql,int qr,int lol,int ror,int cost){
	
	if (l > qr || r < ql)ret ;
	if (ql <= l && r <= qr){
		der[v].pb({{lol,ror},cost});
		ret ;
	}
	int m = l+r>>1;
	update(v<<1,l,m,ql,qr,lol,ror,cost);
	update(v<<1|1,m+1,r,ql,qr,lol,ror,cost);
}

int get_ans(int v,int l,int r,int pos,int x){
	
	int ans=0;
	for (pair<pii,int> z: der[v])
		if (z.fr.fr <= x && x <= z.fr.sc)
			ans += z.sc,xo^=1;
	
	if (l == r)ret ans;
	int m = l+r>>1;
	if (pos > m)
		ret get_ans(v<<1|1,m+1,r,pos,x)+ans;
	ret get_ans(v<<1,l,m,pos,x)+ans;
	
}




main(){
	int n,t,i;
	scanf("%d%d",&n,&t);
	scanf("%s",s+1);
	s[0] = s[n+1] = '0';
	set <int> as;
	for (i=0;i<=n+1;++i)
		if (s[i] == '0')as.insert(i);
	for (i=0;i<=n+1;++i){
		if(s[i] == '0') continue;
		int j=i;
		while(j <= n+1 && s[j] == s[i]) j++;
		update(1, 1, n, i, j-1, i, j-1, 0);
		i = j - 1;
	}
	for (i=1;i<=t;++i){
		char ss[7];
		scanf("%s",ss);
		if (ss[0] == 'q'){
			int l,r;
			scanf("%d%d",&l,&r);
			
			r--;
			xo = 0;
			int ans = get_ans(1,1,n,l,r);
			if (xo)ans += i;
			printf("%d\n",ans);
		}
		else {
			int pos;
			scanf("%d",&pos);
			if (s[pos] == '0'){
				as.erase(pos);
				int l = *--as.upper_bound(pos);
				int r = *as.lower_bound(pos);
				update(1,1,n,l+1,pos,pos,r-1,-i);
				s[pos] = '1';
			} 
			else {
				int l = *--as.upper_bound(pos);
				int r = *as.lower_bound(pos);
				update(1,1,n,l+1,pos,pos,r-1,i);
				s[pos] = '0';
				as.insert(pos);
				
			}
			
		}
	}
	
	
}

Compilation message

street_lamps.cpp: In function 'void update(int, int, int, int, int, int, int, int)':
street_lamps.cpp:33:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m = l+r>>1;
      |          ~^~
street_lamps.cpp: In function 'int get_ans(int, int, int, int, int)':
street_lamps.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m = l+r>>1;
      |          ~^~
street_lamps.cpp: At global scope:
street_lamps.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d%d",&n,&t);
      |  ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~
street_lamps.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%s",ss);
      |   ~~~~~^~~~~~~~~
street_lamps.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |    scanf("%d%d",&l,&r);
      |    ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |    scanf("%d",&pos);
      |    ~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28364 KB Output is correct
2 Correct 16 ms 28424 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 15 ms 28372 KB Output is correct
6 Correct 16 ms 28472 KB Output is correct
7 Correct 16 ms 28488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 33236 KB Output is correct
2 Correct 437 ms 33348 KB Output is correct
3 Correct 272 ms 33952 KB Output is correct
4 Correct 472 ms 43824 KB Output is correct
5 Correct 497 ms 41796 KB Output is correct
6 Correct 505 ms 44664 KB Output is correct
7 Correct 301 ms 43364 KB Output is correct
8 Correct 231 ms 30660 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28492 KB Output is correct
2 Correct 17 ms 28624 KB Output is correct
3 Correct 17 ms 28492 KB Output is correct
4 Correct 16 ms 28364 KB Output is correct
5 Correct 714 ms 46292 KB Output is correct
6 Correct 597 ms 44488 KB Output is correct
7 Correct 483 ms 41120 KB Output is correct
8 Correct 229 ms 30788 KB Output is correct
9 Correct 123 ms 29280 KB Output is correct
10 Correct 133 ms 29380 KB Output is correct
11 Correct 131 ms 29412 KB Output is correct
12 Correct 301 ms 43424 KB Output is correct
13 Correct 223 ms 30664 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28492 KB Output is correct
2 Correct 16 ms 28468 KB Output is correct
3 Correct 16 ms 28540 KB Output is correct
4 Correct 17 ms 28492 KB Output is correct
5 Correct 293 ms 39944 KB Output is correct
6 Correct 417 ms 41924 KB Output is correct
7 Correct 492 ms 44136 KB Output is correct
8 Correct 610 ms 47212 KB Output is correct
9 Correct 333 ms 35028 KB Output is correct
10 Correct 204 ms 35584 KB Output is correct
11 Correct 314 ms 34624 KB Output is correct
12 Correct 213 ms 35884 KB Output is correct
13 Correct 334 ms 35140 KB Output is correct
14 Correct 205 ms 35752 KB Output is correct
15 Correct 323 ms 43448 KB Output is correct
16 Correct 241 ms 30672 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28364 KB Output is correct
2 Correct 16 ms 28424 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 16 ms 28492 KB Output is correct
5 Correct 15 ms 28372 KB Output is correct
6 Correct 16 ms 28472 KB Output is correct
7 Correct 16 ms 28488 KB Output is correct
8 Correct 815 ms 33236 KB Output is correct
9 Correct 437 ms 33348 KB Output is correct
10 Correct 272 ms 33952 KB Output is correct
11 Correct 472 ms 43824 KB Output is correct
12 Correct 497 ms 41796 KB Output is correct
13 Correct 505 ms 44664 KB Output is correct
14 Correct 301 ms 43364 KB Output is correct
15 Correct 231 ms 30660 KB Output is correct
16 Correct 17 ms 28492 KB Output is correct
17 Correct 17 ms 28624 KB Output is correct
18 Correct 17 ms 28492 KB Output is correct
19 Correct 16 ms 28364 KB Output is correct
20 Correct 714 ms 46292 KB Output is correct
21 Correct 597 ms 44488 KB Output is correct
22 Correct 483 ms 41120 KB Output is correct
23 Correct 229 ms 30788 KB Output is correct
24 Correct 123 ms 29280 KB Output is correct
25 Correct 133 ms 29380 KB Output is correct
26 Correct 131 ms 29412 KB Output is correct
27 Correct 301 ms 43424 KB Output is correct
28 Correct 223 ms 30664 KB Output is correct
29 Correct 16 ms 28492 KB Output is correct
30 Correct 16 ms 28468 KB Output is correct
31 Correct 16 ms 28540 KB Output is correct
32 Correct 17 ms 28492 KB Output is correct
33 Correct 293 ms 39944 KB Output is correct
34 Correct 417 ms 41924 KB Output is correct
35 Correct 492 ms 44136 KB Output is correct
36 Correct 610 ms 47212 KB Output is correct
37 Correct 333 ms 35028 KB Output is correct
38 Correct 204 ms 35584 KB Output is correct
39 Correct 314 ms 34624 KB Output is correct
40 Correct 213 ms 35884 KB Output is correct
41 Correct 334 ms 35140 KB Output is correct
42 Correct 205 ms 35752 KB Output is correct
43 Correct 323 ms 43448 KB Output is correct
44 Correct 241 ms 30672 KB Output is correct
45 Correct 3073 ms 31488 KB Output is correct
46 Correct 275 ms 31100 KB Output is correct
47 Correct 243 ms 34968 KB Output is correct
48 Correct 537 ms 43436 KB Output is correct
49 Correct 136 ms 29076 KB Output is correct
50 Correct 138 ms 29036 KB Output is correct
51 Correct 138 ms 29124 KB Output is correct
52 Correct 145 ms 29080 KB Output is correct
53 Correct 146 ms 29012 KB Output is correct
54 Correct 156 ms 28980 KB Output is correct