Submission #172398

#	Time	Username	Problem	Language	Result	Execution time	Memory
172398		dndhk	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2355 ms	312816 KiB

street_lamps

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 300000;

int N, Q;
string str;

set<pii> st;
set<pii>::iterator it1, it2;

int t[MAX_N+1];
struct S{
	int x, y, s, e;
	bool operator <(const S &a)const{
		return s<a.s;
	}
};
vector<S> query;
struct ST{
	int x, y, z;
	bool operator <(const ST &a)const{
		return z<a.z;
	}
};
vector<ST> ask;

struct SEG2{
	struct NODE{
		int l, r;
		int sum;
	};
	int SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x){
		SZ = x;
		add();
	}
	void Update(int x, int y, int z){
		update(0, 1, SZ, x, y, z);
	}
	void update(int idx, int s, int e, int x, int y, int z){
		if(x<=s && e<=y){
			seg[idx].sum+=z;
			return;
		}
		if(x>e || y<s)	return;
		if(seg[idx].l==-1){
			seg[idx].l = seg.size(); add();
		}
		if(seg[idx].r==-1){
			seg[idx].r = seg.size(); add();
		}
		update(seg[idx].l, s, (s+e)/2, x, y, z);
		update(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
	int Calc(int x){
		return calc(0, 1, SZ, x);
	}
	int calc(int idx, int s, int e, int k){
		if(idx==-1)	return 0;
		if(s==e){
			return seg[idx].sum;
		}
		if(k<=(s+e)/2){
			return seg[idx].sum + calc(seg[idx].l, s, (s+e)/2, k);
		}else{
			return seg[idx].sum + calc(seg[idx].r, (s+e)/2+1, e, k);
		}
	}
} S1;
vector<SEG2> Seg2;

struct SEG1{
	struct NODE{
		int l, r, d;
	};
	int SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, -1});
	}
	void Init(int x){
		add();
		SZ = x;
	}
	void Update(int x, int y, int z){
		update(0, 1, SZ, x, y, z);
	}
	void update(int idx, int s, int e, int x, int y, int z){
		if(x<=s && e<=y){
			if(seg[idx].d==-1){
				seg[idx].d = Seg2.size(); 
				Seg2.pb(S1);
				Seg2[seg[idx].d].Init(SZ);
			}
			Seg2[seg[idx].d].Update(x, y, z);
			return;
		}
		if(x>e || y<s)	return;
		if(seg[idx].l==-1){
			seg[idx].l = seg.size(); add();
		}
		if(seg[idx].r==-1){
			seg[idx].r = seg.size(); add();
		}
		update(seg[idx].l, s, (s+e)/2, x, y, z);
		update(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
	int Calc(int x, int y){
		return calc(0, 1, SZ, x, y);
	}
	int calc(int idx, int s, int e, int x, int y){
		if(idx==-1)	return 0;
		int ret = 0;
		if(seg[idx].d!=-1){
			ret+=Seg2[seg[idx].d].Calc(y);
		}
		if(s==e){
			return ret;
		}
		if(x<=(s+e)/2){
			return ret + calc(seg[idx].l, s, (s+e)/2, x, y);
		}else{
			return ret + calc(seg[idx].r, (s+e)/2+1, e, x, y);
		}
	}
} Seg;

void update(int x){
	TEST cout<<"U "<<query[x].x<<" "<<query[x].y<<" "<<query[x].s<<" "<<query[x].e<<endl;
	Seg.Update(query[x].x, query[x].y, query[x].e-query[x].s);
}

int calc(int x, int y){
	return Seg.Calc(x, y);
}

int main(){
	scanf("%d%d", &N, &Q);	
	Seg.Init(N+1);
	cin>>str;
	for(int i=0; i<N; i++){
		if(str[i]=='1'){
			int s = i, e = i;
			while(e<N-1 && str[e+1]=='1')	e++;
			i = e;
			e++;
			st.insert({e+1, s+1});
			t[s+1] = 1;
		}
	}
	for(int i=2; i<=Q+1; i++){
		cin>>str;
		int a, b;
		if(str[0]=='t'){
			scanf("%d", &a);
			it1 = st.upper_bound({a, -1});
			it2 = st.upper_bound({a+1, -1});
			if(it2!=st.end() && (*it2).second<=a){
				int l = (*it2).second, r = (*it2).first;
				query.pb({l, r, t[l], i});
				st.erase({r, l});
				if(l!=a){
					t[l] = i; st.insert({a, l});
				}
				if(r!=a+1){
					t[a+1] = i;
				 	st.insert({r, a+1});
				}
			}else{
				int l = a, r = a+1;
				if(it2!=st.end() && (*it2).second==a+1){
					r = (*it2).first;
					query.pb({a+1, r, t[a+1], i});
					st.erase({r, a+1});
				}
				if(it1!=st.end() && (*it1).first==a){
					l = (*it1).second;
					query.pb({l, a, t[l], i});
					st.erase({a, l});
				}
				t[l] = i;
				st.insert({r, l});
			}
		}else{
			scanf("%d%d", &a, &b);
			ask.pb({a, b, i});
			it1 = st.upper_bound({b, -1});
			if(it1!=st.end() && (*it1).second<=a){
				int l = (*it1).second, r = (*it1).first;
				query.pb({l, r, t[l], i});
				t[l] = i;
			}
		}
	}
	sort(query.begin(), query.end());
	int idx = 0, idx2 = 0;
	while(idx<query.size() && query[idx].s==1){
		update(idx);
		idx++;
	}
	for(int i=2; i<=Q+1; i++){
		if(idx2<ask.size() && ask[idx2].z==i){
			TEST cout<<"Q "<<ask[idx2].x<<" "<<ask[idx2].y<<endl;
			printf("%d\n", calc(ask[idx2].x, ask[idx2].y));
			idx2++;
		}
		while(idx<query.size() && query[idx].s<=i){
			update(idx);
			idx++;
		}
	}
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:223:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx<query.size() && query[idx].s==1){
        ~~~^~~~~~~~~~~~~
street_lamps.cpp:228:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx2<ask.size() && ask[idx2].z==i){
      ~~~~^~~~~~~~~~~
street_lamps.cpp:233:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx<query.size() && query[idx].s<=i){
         ~~~^~~~~~~~~~~~~
street_lamps.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q); 
  ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:181:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:211:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20