답안 #336666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336666 2020-12-16T09:51:47 Z errorgorn 가로등 (APIO19_street_lamps) C++17
100 / 100
2754 ms 95344 KB
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct U{
	int typ;
	int a,b;
	int t;
	int id;
};

int n,q;
string st;
set<ii> s;
vector<U> upd;
int ans[300005];

void add(ii range, int t){
	s.insert(range);
	upd.push_back({1,range.fi,range.se,t,1});
}

void rem(ii range,int t){
	s.erase(range);
	upd.push_back({1,range.fi,range.se,t,-1});
}

int fen[300005];

void inc(int i,int j){
	while (i<=300005){
		fen[i]+=j;
		i+=i&-i;
	}
}

int query(int i){
	int res=0;
	while (i){
		res+=fen[i];
		i-=i&-i;
	}
	return res;
}

void dnc(int l,int r,vector<U> upd){
	int m=l+r>>1;
	vector<U> lupd,rupd;
	set<int> s;
	
	//cout<<"rec: "<<l<<" "<<r<<" "<<sz(upd)<<endl;
	
	for (auto &it:upd){
		if (it.typ==1){ //upd
			if (it.id==1){ //adding
				inc(it.a,-it.t);
				s.insert(it.a);
			}
			else{ //erasing
				inc(it.a,it.t);
				s.erase(it.a);
			}
			
			if (it.b<=m) lupd.push_back(it);
			else rupd.push_back(it);
		}
		else{
			//cout<<"debug: "<<it.b<<endl;
			if (it.b<=l){ //[l,r] completely in [it.b,N]
				//cout<<l<<" "<<r<<" "<<it.id<<endl;
				ans[it.id]+=query(it.a);
				if (!s.empty() && *s.begin()<=it.a) ans[it.id]+=it.t;
			}
			else{
				if (it.b<=m) lupd.push_back(it);
				rupd.push_back(it);
			}
		}
	}
	
	//reset fenwick
	for (auto &it:upd){
		if (it.typ==1) inc(it.a,it.t*it.id);
	}
	
	if (l==r) return;
	dnc(l,m,lupd);
	dnc(m+1,r,rupd);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	cin>>st;
	st="$"+st;
	
	ii curr=ii(-1,-1);
	rep(x,1,sz(st)){
		if (st[x]=='1'){
			if (curr.fi==-1) curr.fi=x;
			curr.se=x;
		}
		else{
			if (curr.fi!=-1){
				add(curr,0);
				curr=ii(-1,-1);
			}
		}
	}
	
	if (curr!=ii(-1,-1)){
		add(curr,0);
	}
	
	string typ;
	int a,b;
	int IDX=0;
	
	rep(x,1,q+1){
		cin>>typ;
		
		if (typ=="query"){
			cin>>a>>b;
			
			upd.push_back({2,a,b-1,x,IDX++});
		}
		else{
			cin>>a;
			
			if (st[a]=='0'){
				ii range=ii(a,a);
				auto it=s.lower_bound(ii(a,-1));
				if (it!=s.end() && (*it).fi==a+1) range.se=(*it).se;
				if (it!=s.begin() && (*prev(it)).se==a-1) range.fi=(*prev(it)).fi;
				
				if (range.fi!=a) rem(ii(range.fi,a-1),x);
				if (range.se!=a) rem(ii(a+1,range.se),x);
				add(range,x);
				
				st[a]='1';
			}
			else{
				ii range=*--s.lower_bound(ii(a,1e9));
				
				rem(range,x);
				if (range.fi!=a) add(ii(range.fi,a-1),x);
				if (range.se!=a) add(ii(a+1,range.se),x);
				
				st[a]='0';
			}
			
			//for (auto &it:s) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
		}
	}
	
	dnc(1,n,upd);
	rep(x,0,IDX) cout<<ans[x]<<endl;
}

Compilation message

street_lamps.cpp: In function 'void add(std::pair<long long int, long long int>, int)':
street_lamps.cpp:14:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
   14 | #define fi first
      |            ^
street_lamps.cpp:43:25: note: in expansion of macro 'fi'
   43 |  upd.push_back({1,range.fi,range.se,t,1});
      |                         ^~
street_lamps.cpp:15:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
   15 | #define se second
      |            ^
street_lamps.cpp:43:34: note: in expansion of macro 'se'
   43 |  upd.push_back({1,range.fi,range.se,t,1});
      |                                  ^~
street_lamps.cpp: In function 'void rem(std::pair<long long int, long long int>, int)':
street_lamps.cpp:14:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
   14 | #define fi first
      |            ^
street_lamps.cpp:48:25: note: in expansion of macro 'fi'
   48 |  upd.push_back({1,range.fi,range.se,t,-1});
      |                         ^~
street_lamps.cpp:15:12: warning: narrowing conversion of 'range.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
   15 | #define se second
      |            ^
street_lamps.cpp:48:34: note: in expansion of macro 'se'
   48 |  upd.push_back({1,range.fi,range.se,t,-1});
      |                                  ^~
street_lamps.cpp: In function 'void dnc(int, int, std::vector<U>)':
street_lamps.cpp:70:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int m=l+r>>1;
      |        ~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 493 ms 56384 KB Output is correct
2 Correct 603 ms 58712 KB Output is correct
3 Correct 882 ms 60408 KB Output is correct
4 Correct 1893 ms 83748 KB Output is correct
5 Correct 1765 ms 81728 KB Output is correct
6 Correct 1974 ms 87200 KB Output is correct
7 Correct 411 ms 57400 KB Output is correct
8 Correct 406 ms 53956 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2464 ms 73660 KB Output is correct
6 Correct 2336 ms 80036 KB Output is correct
7 Correct 1836 ms 78496 KB Output is correct
8 Correct 401 ms 62264 KB Output is correct
9 Correct 131 ms 44568 KB Output is correct
10 Correct 143 ms 49480 KB Output is correct
11 Correct 143 ms 49568 KB Output is correct
12 Correct 386 ms 60852 KB Output is correct
13 Correct 394 ms 60728 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 732 ms 82616 KB Output is correct
6 Correct 1351 ms 82616 KB Output is correct
7 Correct 1963 ms 87736 KB Output is correct
8 Correct 2754 ms 95344 KB Output is correct
9 Correct 750 ms 63408 KB Output is correct
10 Correct 730 ms 68780 KB Output is correct
11 Correct 765 ms 64584 KB Output is correct
12 Correct 721 ms 75568 KB Output is correct
13 Correct 747 ms 63668 KB Output is correct
14 Correct 725 ms 75564 KB Output is correct
15 Correct 391 ms 60760 KB Output is correct
16 Correct 398 ms 61452 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 493 ms 56384 KB Output is correct
9 Correct 603 ms 58712 KB Output is correct
10 Correct 882 ms 60408 KB Output is correct
11 Correct 1893 ms 83748 KB Output is correct
12 Correct 1765 ms 81728 KB Output is correct
13 Correct 1974 ms 87200 KB Output is correct
14 Correct 411 ms 57400 KB Output is correct
15 Correct 406 ms 53956 KB Output is correct
16 Correct 6 ms 620 KB Output is correct
17 Correct 5 ms 748 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 2 ms 620 KB Output is correct
20 Correct 2464 ms 73660 KB Output is correct
21 Correct 2336 ms 80036 KB Output is correct
22 Correct 1836 ms 78496 KB Output is correct
23 Correct 401 ms 62264 KB Output is correct
24 Correct 131 ms 44568 KB Output is correct
25 Correct 143 ms 49480 KB Output is correct
26 Correct 143 ms 49568 KB Output is correct
27 Correct 386 ms 60852 KB Output is correct
28 Correct 394 ms 60728 KB Output is correct
29 Correct 2 ms 620 KB Output is correct
30 Correct 3 ms 748 KB Output is correct
31 Correct 5 ms 748 KB Output is correct
32 Correct 6 ms 748 KB Output is correct
33 Correct 732 ms 82616 KB Output is correct
34 Correct 1351 ms 82616 KB Output is correct
35 Correct 1963 ms 87736 KB Output is correct
36 Correct 2754 ms 95344 KB Output is correct
37 Correct 750 ms 63408 KB Output is correct
38 Correct 730 ms 68780 KB Output is correct
39 Correct 765 ms 64584 KB Output is correct
40 Correct 721 ms 75568 KB Output is correct
41 Correct 747 ms 63668 KB Output is correct
42 Correct 725 ms 75564 KB Output is correct
43 Correct 391 ms 60760 KB Output is correct
44 Correct 398 ms 61452 KB Output is correct
45 Correct 210 ms 37576 KB Output is correct
46 Correct 320 ms 40648 KB Output is correct
47 Correct 949 ms 49044 KB Output is correct
48 Correct 1871 ms 82996 KB Output is correct
49 Correct 158 ms 54472 KB Output is correct
50 Correct 156 ms 54088 KB Output is correct
51 Correct 160 ms 54724 KB Output is correct
52 Correct 169 ms 55368 KB Output is correct
53 Correct 167 ms 55112 KB Output is correct
54 Correct 169 ms 55276 KB Output is correct