oj.uz

Submission #146316

# Submission time Handle Problem Language Result Execution time Memory
146316 2019-08-23T12:39:51 Z username Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4988 ms 126848 KB 
#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define F first
#define S second
#define endl '\n'
//																#define __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
struct OP{int o,l,r,t,d;};
const int maxn=3e5+9;
int n,q,p=0,res[maxn];
OP ops[4*maxn],t[4*maxn];
set<int>st;

void cdq2(int l,int r){
	if(l+1==r)return;
	cdq2(l,mid),cdq2(mid,r);
	REP(i,l,mid)t[i].r=0;
	REP(i,mid,r)t[i].r=1;
	inplace_merge(t+l,t+mid,t+r,[](OP a,OP b){return a.t<b.t;});
	int c=0;
	REP(i,l,r){
		OP&oo=t[i];
		if(!oo.o&&!oo.l&&!oo.r)c+=oo.d*(q-1-oo.t);
		if(oo.o&&oo.l&&oo.r)res[oo.t]+=c;
	}
}

void cdq1(int l,int r){
	if(l+1==r)return;
	cdq1(l,mid),cdq1(mid,r);
	REP(i,l,mid)ops[i].l=0;
	REP(i,mid,r)ops[i].l=1;
	inplace_merge(ops+l,ops+mid,ops+r,[](OP a,OP b){return a.r==b.r?a.o<b.o:a.r>b.r;});
	REP(i,l,r)t[i]=ops[i];
	cdq2(l,r);
}

main(){
	IOS;
	cin>>n>>q;
	st.insert(-1);
	REP(i,0,n){
		char c;cin>>c;
		if(c=='0')st.insert(i);
		else{
			if(p&&ops[p-1].r==i-1)ops[p-1].r=i;
			else{
				ops[p++]=OP{0,*st.rbegin()+1,i-1,-1,-1};
				ops[p++]=OP{0,*st.rbegin()+1,i,-1,1};
			}
		}
	}
	st.insert(n);
	REP(t,0,q){
		string cmd;cin>>cmd;
		if(cmd[0]=='t'){
			int i,x;cin>>i,--i;
			x=st.count(i)?1:-1;
			if(x<0)st.insert(i);
			auto it=st.find(i);
			ops[p++]=OP{0,*prev(it)+1,*next(it)-1,t,x};
			ops[p++]=OP{0,*prev(it)+1,i-1,t,-x};
			ops[p++]=OP{0,i+1,*next(it)-1,t,-x};
			if(x>0)st.erase(it);
			res[t]=-1;
		}else{
			int a,b;cin>>a>>b,--a,--b;
			ops[p++]=OP{1,a,b-1,t,0};
			auto it=st.lower_bound(a);
			if(it!=st.end()&&*it>=b)res[t]-=q-1-t;
		}
	}
	sort(ops,ops+p,[](OP a,OP b){return a.l==b.l?a.o<b.o:a.l<b.l;});
	cdq1(0,p);
	REP(i,0,q)if(res[i]>=0)cout<<res[i]<<endl;
}

Compilation message

street_lamps.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2979 ms 67992 KB Output is correct
2 Correct 3055 ms 71016 KB Output is correct
3 Correct 3236 ms 71784 KB Output is correct
4 Correct 4070 ms 95816 KB Output is correct
5 Correct 4074 ms 87376 KB Output is correct
6 Correct 3979 ms 102012 KB Output is correct
7 Correct 1746 ms 55212 KB Output is correct
8 Correct 1428 ms 41104 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 9 ms 760 KB Output is correct
3 Correct 8 ms 632 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 4612 ms 117948 KB Output is correct
6 Correct 4581 ms 108640 KB Output is correct
7 Correct 3858 ms 87320 KB Output is correct
8 Correct 1711 ms 41104 KB Output is correct
9 Correct 972 ms 31256 KB Output is correct
10 Correct 1108 ms 34324 KB Output is correct
11 Correct 1027 ms 34244 KB Output is correct
12 Correct 2039 ms 55192 KB Output is correct
13 Correct 1741 ms 41196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 9 ms 760 KB Output is correct
4 Correct 13 ms 760 KB Output is correct
5 Correct 2635 ms 64868 KB Output is correct
6 Correct 3361 ms 83164 KB Output is correct
7 Correct 4049 ms 102016 KB Output is correct
8 Correct 4988 ms 126848 KB Output is correct
9 Correct 3641 ms 85844 KB Output is correct
10 Correct 4301 ms 101568 KB Output is correct
11 Correct 3658 ms 85976 KB Output is correct
12 Correct 4343 ms 101668 KB Output is correct
13 Correct 3649 ms 85852 KB Output is correct
14 Correct 4305 ms 101576 KB Output is correct
15 Correct 2083 ms 55180 KB Output is correct
16 Correct 1721 ms 41080 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2979 ms 67992 KB Output is correct
9 Correct 3055 ms 71016 KB Output is correct
10 Correct 3236 ms 71784 KB Output is correct
11 Correct 4070 ms 95816 KB Output is correct
12 Correct 4074 ms 87376 KB Output is correct
13 Correct 3979 ms 102012 KB Output is correct
14 Correct 1746 ms 55212 KB Output is correct
15 Correct 1428 ms 41104 KB Output is correct
16 Correct 8 ms 760 KB Output is correct
17 Correct 9 ms 760 KB Output is correct
18 Correct 8 ms 632 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 4612 ms 117948 KB Output is correct
21 Correct 4581 ms 108640 KB Output is correct
22 Correct 3858 ms 87320 KB Output is correct
23 Correct 1711 ms 41104 KB Output is correct
24 Correct 972 ms 31256 KB Output is correct
25 Correct 1108 ms 34324 KB Output is correct
26 Correct 1027 ms 34244 KB Output is correct
27 Correct 2039 ms 55192 KB Output is correct
28 Correct 1741 ms 41196 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 7 ms 632 KB Output is correct
31 Correct 9 ms 760 KB Output is correct
32 Correct 13 ms 760 KB Output is correct
33 Correct 2635 ms 64868 KB Output is correct
34 Correct 3361 ms 83164 KB Output is correct
35 Correct 4049 ms 102016 KB Output is correct
36 Correct 4988 ms 126848 KB Output is correct
37 Correct 3641 ms 85844 KB Output is correct
38 Correct 4301 ms 101568 KB Output is correct
39 Correct 3658 ms 85976 KB Output is correct
40 Correct 4343 ms 101668 KB Output is correct
41 Correct 3649 ms 85852 KB Output is correct
42 Correct 4305 ms 101576 KB Output is correct
43 Correct 2083 ms 55180 KB Output is correct
44 Correct 1721 ms 41080 KB Output is correct
45 Correct 1753 ms 47148 KB Output is correct
46 Correct 1912 ms 47308 KB Output is correct
47 Correct 2203 ms 55908 KB Output is correct
48 Correct 3899 ms 95640 KB Output is correct
49 Correct 1249 ms 38480 KB Output is correct
50 Correct 1265 ms 38652 KB Output is correct
51 Correct 1221 ms 38784 KB Output is correct
52 Correct 1086 ms 39308 KB Output is correct
53 Correct 1104 ms 38996 KB Output is correct
54 Correct 1095 ms 39112 KB Output is correct