oj.uz

Submission #997947

# Submission time Handle Problem Language Result Execution time Memory
997947 2024-06-13T07:09:14 Z pcc Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2098 ms 65688 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 3e5+10;

int N;
int q;
vector<pair<int,pii>> req;
int ans[mxn];
string state;

struct Q{
	int tp,s,e,val;
	Q(int tt,int ss,int ee,int vv):tp(tt),s(ss),e(ee),val(vv){}
	bool operator<(Q &b)const{
		return s==b.s?tp<b.tp:s<b.s;
	}
};

struct BIT{
	BIT(){}
	int bit[mxn];
	void modify(int p,int v){
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e){
		if(e == -1)swap(s,e);
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}	
};


vector<Q> v;

namespace INIT{
	set<int> st;
	void GO(){
		st.insert(0);
		st.insert(N+1);
		for(int i = 1;i<=N;i++){
			if(state[i] == '0'){
				st.insert(i);
			}
		}
		for(auto it = next(st.begin());it != st.end();it++){
			int pre = *prev(it)+1;
			int now = *it;
			v.push_back(Q(-1,pre,now,1));
		}
		for(int i = 0;i<q;i++){
			int t = req[i].fs;
			if(t == 0){
				int id = req[i].sc.fs;
				if(st.find(id) == st.end()){
					auto rp = *st.upper_bound(id);
					auto lp = *(--st.upper_bound(id))+1;
					v.push_back(Q(-1,lp,rp,i));
					v.push_back(Q(-1,lp,id,-i));
					v.push_back(Q(-1,id+1,rp,-i));
					st.insert(id);
				}
				else{
					st.erase(id);
					auto rp = *st.upper_bound(id);
					auto lp = *(--st.upper_bound(id))+1;
					v.push_back(Q(-1,lp,id,i));
					v.push_back(Q(-1,id+1,rp,i));
					v.push_back(Q(-1,lp,rp,-i));
				}
			}
			else{
				auto [s,e] = req[i].sc;
				int sh = 0;
				if(*st.lower_bound(s)>=e)sh += i;
				v.push_back(Q(i,s,e,sh));
				ans[i] += sh;
			}
		}
		return;
	}
	void DEBUG(){
		for(auto &i:v){
			cout<<i.tp<<','<<i.s<<' '<<i.e<<' '<<i.val<<endl;
		}
		return;
	}
}

namespace CDQ{
	BIT bit;
	void dc(int l,int r){
		if(l == r)return;
		int mid = (l+r)>>1;
		dc(l,mid);dc(mid+1,r);
		vector<Q> tv;
		vector<int> used = {1};
		for(int i = l;i<=mid;i++){
			if(v[i].tp == -1)tv.push_back(v[i]);
		}
		for(int i = mid+1;i<=r;i++){
			if(v[i].tp != -1)tv.push_back(v[i]);
		}
		sort(tv.begin(),tv.end());
		for(auto &i:tv){
			if(i.tp == -1){
				bit.modify(1,i.val);
				bit.modify(i.e+1,-i.val);
				used.push_back(i.e+1);
			}
			else{
				ans[i.tp] += bit.getval(0,i.e);
			}
		}
		for(auto &i:used)bit.modify(i,-bit.getval(i,i));
		return;
	}

	void GO(){
		dc(0,v.size()-1);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>q;
	cin>>state;
	state = "#"+state;
	for(int i = 0;i<q;i++){
		string s;
		cin>>s;
		if(s[0] == 't'){
			int id;
			cin>>id;
			req.push_back(make_pair(0,pii(id,id)));
		}
		else{
			int s,e;
			cin>>s>>e;
			req.push_back(make_pair(1,pii(s,e)));
		}
	}
	INIT::GO();
	CDQ::GO();
	for(int i = 0;i<q;i++){
		if(req[i].fs)cout<<ans[i]<<'\n';
	}
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 34024 KB Output is correct
2 Correct 811 ms 34484 KB Output is correct
3 Correct 907 ms 34720 KB Output is correct
4 Correct 1367 ms 47920 KB Output is correct
5 Correct 1083 ms 43452 KB Output is correct
6 Correct 1462 ms 58288 KB Output is correct
7 Correct 868 ms 64424 KB Output is correct
8 Correct 236 ms 26288 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2098 ms 65688 KB Output is correct
6 Correct 1609 ms 50856 KB Output is correct
7 Correct 1053 ms 41820 KB Output is correct
8 Correct 242 ms 28324 KB Output is correct
9 Correct 142 ms 15708 KB Output is correct
10 Correct 124 ms 23736 KB Output is correct
11 Correct 124 ms 22968 KB Output is correct
12 Correct 852 ms 64400 KB Output is correct
13 Correct 254 ms 26544 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2524 KB Output is correct
4 Correct 4 ms 2716 KB Output is correct
5 Correct 624 ms 42860 KB Output is correct
6 Correct 1028 ms 56236 KB Output is correct
7 Correct 1479 ms 59096 KB Output is correct
8 Correct 1888 ms 60316 KB Output is correct
9 Correct 1097 ms 39096 KB Output is correct
10 Correct 1255 ms 41128 KB Output is correct
11 Correct 1079 ms 39236 KB Output is correct
12 Correct 1310 ms 41632 KB Output is correct
13 Correct 1027 ms 39692 KB Output is correct
14 Correct 1242 ms 40640 KB Output is correct
15 Correct 835 ms 62212 KB Output is correct
16 Correct 227 ms 27824 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 817 ms 34024 KB Output is correct
9 Correct 811 ms 34484 KB Output is correct
10 Correct 907 ms 34720 KB Output is correct
11 Correct 1367 ms 47920 KB Output is correct
12 Correct 1083 ms 43452 KB Output is correct
13 Correct 1462 ms 58288 KB Output is correct
14 Correct 868 ms 64424 KB Output is correct
15 Correct 236 ms 26288 KB Output is correct
16 Correct 4 ms 2652 KB Output is correct
17 Correct 3 ms 2652 KB Output is correct
18 Correct 3 ms 2652 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 2098 ms 65688 KB Output is correct
21 Correct 1609 ms 50856 KB Output is correct
22 Correct 1053 ms 41820 KB Output is correct
23 Correct 242 ms 28324 KB Output is correct
24 Correct 142 ms 15708 KB Output is correct
25 Correct 124 ms 23736 KB Output is correct
26 Correct 124 ms 22968 KB Output is correct
27 Correct 852 ms 64400 KB Output is correct
28 Correct 254 ms 26544 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 2 ms 2652 KB Output is correct
31 Correct 3 ms 2524 KB Output is correct
32 Correct 4 ms 2716 KB Output is correct
33 Correct 624 ms 42860 KB Output is correct
34 Correct 1028 ms 56236 KB Output is correct
35 Correct 1479 ms 59096 KB Output is correct
36 Correct 1888 ms 60316 KB Output is correct
37 Correct 1097 ms 39096 KB Output is correct
38 Correct 1255 ms 41128 KB Output is correct
39 Correct 1079 ms 39236 KB Output is correct
40 Correct 1310 ms 41632 KB Output is correct
41 Correct 1027 ms 39692 KB Output is correct
42 Correct 1242 ms 40640 KB Output is correct
43 Correct 835 ms 62212 KB Output is correct
44 Correct 227 ms 27824 KB Output is correct
45 Correct 515 ms 22340 KB Output is correct
46 Correct 491 ms 20916 KB Output is correct
47 Correct 734 ms 26808 KB Output is correct
48 Correct 1255 ms 47780 KB Output is correct
49 Correct 147 ms 23732 KB Output is correct
50 Correct 146 ms 23992 KB Output is correct
51 Correct 161 ms 24508 KB Output is correct
52 Correct 147 ms 24888 KB Output is correct
53 Correct 162 ms 24752 KB Output is correct
54 Correct 140 ms 25528 KB Output is correct