oj.uz

Submission #136607

# Submission time Handle Problem Language Result Execution time Memory
136607 2019-07-25T18:04:37 Z liwi Street Lamps (APIO19_street_lamps) C++11
100 / 100
 4773 ms 224444 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 300005
#define MAXS 14000000

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int cnt;

struct node{
//	int l,r;
	int lft,rgt;
//	ll lazy0,lazy1;
	int sum;
	short cnt; //lazy0 for sum, lazy1 for cnt
//	node *lft,*rgt;
//
//	node(int l, int r){
//		this->l = l;
//		this->r = r;
//		this->lazy0 = this->lazy1 = this->sum = this->cnt = 0;
//		lft = rgt = 0;
//	}
};

int len,num_q,arr[MAXN],rt[MAXN];
node seg[MAXS];
set<int> zeros;
//
//inline void build_needed(int rt){
//	if(!seg[rt].lft){
//		seg[rt].lft = ++cnt;
//		seg[cnt] = {0,0,0,0};
//	}
//	if(!seg[rt].rgt){
//		seg[rt].rgt = ++cnt;
//		seg[cnt] = {0,0,0,0};
//	}
//}

//inline void push_down(int rt){
//	build_needed(rt);
//	seg[seg[rt].lft].lazy0+=seg[rt].lazy0, seg[seg[rt].rgt].lazy0+=seg[rt].lazy0;
//	seg[seg[rt].lft].sum+=seg[rt].lazy0, seg[seg[rt].rgt].sum+=seg[rt].lazy0;
//
//	seg[seg[rt].lft].lazy1+=seg[rt].lazy1, seg[seg[rt].rgt].lazy1+=seg[rt].lazy1;
//	seg[seg[rt].lft].cnt+=seg[rt].lazy1, seg[seg[rt].rgt].cnt+=seg[rt].lazy1;
//
//	seg[rt].lazy0 = seg[rt].lazy1 = 0;
//}

void update(int sl, int sr, int pos, int rt, int sumv, int cntv){
	if(sl == sr){
		seg[rt].sum+=sumv;
		seg[rt].cnt+=cntv;
		return;
	}
//	if(seg[rt].lazy0 || seg[rt].lazy1) push_down(rt);
//	build_needed(rt);
	int mid = (sl+sr)>>1;
	if(pos <= mid){
		if(!seg[rt].lft){
			seg[rt].lft = ++cnt;
			seg[cnt] = {0,0,0,0};
		}
		update(sl,mid,pos,seg[rt].lft,sumv,cntv);
	}else{
		if(!seg[rt].rgt){
			seg[rt].rgt = ++cnt;
			seg[cnt] = {0,0,0,0};
		}
		update(mid+1,sr,pos,seg[rt].rgt,sumv,cntv);
	}
	seg[rt].sum = seg[seg[rt].lft].sum+seg[seg[rt].rgt].sum;
	seg[rt].cnt = seg[seg[rt].lft].cnt+seg[seg[rt].rgt].cnt;
}

pll query(int sl, int sr, int pos, int rt){
	if(sl == sr){
		return mp(seg[rt].sum,seg[rt].cnt);
//		if(s == 0) return seg[rt].sum;
//		return seg[rt].cnt;
	}
//	if(seg[rt].lazy0 || seg[rt].lazy1) push_down(rt);
//	build_needed(rt);
	int mid = (sl+sr)>>1;
	if(pos <= mid){
		if(!seg[rt].lft) return mp(0,0);
		return query(sl,mid,pos,seg[rt].lft);
	}
	if(!seg[rt].rgt) return mp(seg[seg[rt].lft].sum,seg[seg[rt].lft].cnt);
	pll t = query(mid+1,sr,pos,seg[rt].rgt);
	t.first+=seg[seg[rt].lft].sum;
	t.second+=seg[seg[rt].lft].cnt;
	return t;
}

inline void bupdate(int xl, int xr, int l, int r, int sv, int cv){
//	for(int i=xl; i<=xr; i++)
//		bit[i].update(l,r,bit[i].rt,v);
	for(int i=xl; i<=len+1; i+=i&-i){
		if(!rt[i]){
			rt[i] = ++cnt;
			seg[cnt] = {0,0,0,0};
		}
		update(1,len+1,l,rt[i],sv,cv);
		if(r+1 <= len+1)
			update(1,len+1,r+1,rt[i],-sv,-cv);
	}
//		bit[i].update(l,r,bit[i].rt,v,s);
//	if(r < len+1){
		for(int i=xr+1; i<=len+1; i+=i&-i){
			if(!rt[i]){
				rt[i] = ++cnt;
				seg[cnt] = {0,0,0,0};
			}
			update(1,len+1,l,rt[i],-sv,-cv);
			if(r+1 <= len+1)
				update(1,len+1,r+1,rt[i],sv,cv);
//		update(1,len+1,l,r,rt[i],-v,s);
		}
//	}
//		bit[i].update(l,r,bit[i].rt,-v,s);
}

inline pll bquery(int a, int b){
	pll res = mp(0,0); //sum,cnt
//	res = bit[a].query(b,bit[a].rt);
	for(int i=a; i>0; i-=i&-i){
		if(!rt[i]) continue;
		pll t = query(1,len+1,b,rt[i]);
		res.first+=t.first;
		res.second+=t.second;
	}
//		res+=bit[i].query(b,bit[i].rt,s);
	return res;
}

//inline void cupdate(int xl, int xr, int l, int r, ll v){
////	for(int i=xl; i<=xr; i++)
////		cnt[i].update(l,r,cnt[i].rt,v);
//	for(int i=xl; i<=len+1; i+=i&-i)
//		cnt[i].update(l,r,cnt[i].rt,v);
//	for(int i=xr+1; i<=len+1; i+=i&-i)
//		cnt[i].update(l,r,cnt[i].rt,-v);
//}
//
//inline ll cquery(int a, int b){
//	ll res = 0;
////	res = cnt[a].query(b,cnt[a].rt);
//	for(int i=a; i>0; i-=i&-i)
//		res+=cnt[i].query(b,cnt[i].rt);
//	return res;
//}

int main(){
//	freopen("28","r",stdin);
//	fastio; cin>>len>>num_q;
	scanf("%d %d",&len,&num_q);
	for(int i=1; i<=len; i++){
		char c; scanf(" %c",&c); // cin>>c;
		arr[i] = c-'0';
	}
//	for(int i=1; i<=len+1; i++){
//		rt[i] = ++cnt;
//		seg[cnt] = {0,0,0,0};
////		bit[i].rt = new node(1,len+1);
////		cnt[i].rt = new node(1,len+1,0,0);
////		bit[i].build(1,len+1,1);
////		cnt[i].build(1,len+1,1);
//	}
	zeros.insert(0); zeros.insert(len+1);
//	cupdate(1,len+1,1,len+1,1);
	bupdate(1,len+1,1,len+1,0,1);
	int lst = 0;
	for(int a=1; a<=len; a++){
		if(arr[a] == 0){
			zeros.insert(a);
			int l = lst, r = len+1;
//			update(bit,l+1,a,a+1,r-1,i);
//			cupdate(l+1,a,a+1,r,-1);
			bupdate(l+1,a,a+1,r,0,-1);
			lst = a;
//			printf("R1: %d   R2: %d    C1: %d    C2: %d    V: %d\n",l+1,a,a+1,r,-1);
		}
	}
	for(int i=1; i<=num_q; i++){
		char op[10]; int a; scanf(" %s %d",op,&a);
//		string op; int a; cin>>op>>a;
		if(op[0] == 't'){
//			int l; // = *(--zeros.lower_bound(a));
			auto rit = zeros.upper_bound(a);
			if(arr[a] == 0){
				int r = *rit;
				int l = *(----rit);
				bupdate(l+1,a,a+1,r,-i,1);
//				bupdate(l+1,a,a+1,r,1,1);
				zeros.erase(a);
				//(previous value)+(t-i)
				//(previous value)+t-i
			}else{
				int r = *rit;
				int l = *(--rit);
				bupdate(l+1,a,a+1,r,i,-1);
//				bupdate(l+1,a,a+1,r,-1,1);
				zeros.insert(a);
				//(previous value)-(t-i)
				//(previous value)-t+i
			}
			arr[a] = !arr[a];
		}else{
			int b; scanf(" %d",&b); //cin>>b;
			pll t = bquery(a,b);
			ll f = t.second*i;
			ll s = t.first;
//			if(f+s < 0) assert(false);
//			cout<<f+s<<endl;
			printf("%lld\n",f+s);
		}
	}
//	cout<<"lol"<<endl;
}
/*
5 1
11111
query 1 2
ans=1

5 4
00001
toggle 3
toggle 2
toggle 4
query 2 6
ans=1
 */

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:201:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&len,&num_q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:203:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c",&c); // cin>>c;
           ~~~~~^~~~~~~~~~
street_lamps.cpp:230:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char op[10]; int a; scanf(" %s %d",op,&a);
                       ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:254:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int b; scanf(" %d",&b); //cin>>b;
           ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 1380 KB Output is correct
2 Correct 355 ms 1568 KB Output is correct
3 Correct 727 ms 4612 KB Output is correct
4 Correct 2913 ms 167820 KB Output is correct
5 Correct 2568 ms 136060 KB Output is correct
6 Correct 3182 ms 172644 KB Output is correct
7 Correct 2019 ms 199648 KB Output is correct
8 Correct 183 ms 3576 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 888 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4773 ms 224444 KB Output is correct
6 Correct 3531 ms 186912 KB Output is correct
7 Correct 2147 ms 135424 KB Output is correct
8 Correct 182 ms 3576 KB Output is correct
9 Correct 112 ms 1340 KB Output is correct
10 Correct 122 ms 1284 KB Output is correct
11 Correct 121 ms 1404 KB Output is correct
12 Correct 1273 ms 199892 KB Output is correct
13 Correct 182 ms 3544 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 829 ms 135376 KB Output is correct
6 Correct 1802 ms 157012 KB Output is correct
7 Correct 2881 ms 172440 KB Output is correct
8 Correct 4268 ms 186256 KB Output is correct
9 Correct 417 ms 868 KB Output is correct
10 Correct 336 ms 512 KB Output is correct
11 Correct 414 ms 864 KB Output is correct
12 Correct 339 ms 504 KB Output is correct
13 Correct 420 ms 764 KB Output is correct
14 Correct 338 ms 508 KB Output is correct
15 Correct 1311 ms 199844 KB Output is correct
16 Correct 183 ms 3576 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 272 ms 1380 KB Output is correct
9 Correct 355 ms 1568 KB Output is correct
10 Correct 727 ms 4612 KB Output is correct
11 Correct 2913 ms 167820 KB Output is correct
12 Correct 2568 ms 136060 KB Output is correct
13 Correct 3182 ms 172644 KB Output is correct
14 Correct 2019 ms 199648 KB Output is correct
15 Correct 183 ms 3576 KB Output is correct
16 Correct 5 ms 888 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 4 ms 632 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 4773 ms 224444 KB Output is correct
21 Correct 3531 ms 186912 KB Output is correct
22 Correct 2147 ms 135424 KB Output is correct
23 Correct 182 ms 3576 KB Output is correct
24 Correct 112 ms 1340 KB Output is correct
25 Correct 122 ms 1284 KB Output is correct
26 Correct 121 ms 1404 KB Output is correct
27 Correct 1273 ms 199892 KB Output is correct
28 Correct 182 ms 3544 KB Output is correct
29 Correct 3 ms 632 KB Output is correct
30 Correct 4 ms 632 KB Output is correct
31 Correct 4 ms 632 KB Output is correct
32 Correct 5 ms 760 KB Output is correct
33 Correct 829 ms 135376 KB Output is correct
34 Correct 1802 ms 157012 KB Output is correct
35 Correct 2881 ms 172440 KB Output is correct
36 Correct 4268 ms 186256 KB Output is correct
37 Correct 417 ms 868 KB Output is correct
38 Correct 336 ms 512 KB Output is correct
39 Correct 414 ms 864 KB Output is correct
40 Correct 339 ms 504 KB Output is correct
41 Correct 420 ms 764 KB Output is correct
42 Correct 338 ms 508 KB Output is correct
43 Correct 1311 ms 199844 KB Output is correct
44 Correct 183 ms 3576 KB Output is correct
45 Correct 101 ms 996 KB Output is correct
46 Correct 174 ms 632 KB Output is correct
47 Correct 1255 ms 57720 KB Output is correct
48 Correct 2601 ms 168040 KB Output is correct
49 Correct 128 ms 1136 KB Output is correct
50 Correct 128 ms 1016 KB Output is correct
51 Correct 129 ms 1132 KB Output is correct
52 Correct 131 ms 1016 KB Output is correct
53 Correct 133 ms 1128 KB Output is correct
54 Correct 133 ms 1016 KB Output is correct