Submission #231151

#	Time	Username	Problem	Language	Result	Execution time	Memory
231151		ChrisT	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1510 ms	83640 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define lc ind<<1
#define rc ind<<1|1
const int MN = 3e5+4, MOD = 1e9+7, BASE = 31;
struct Q {
	int x,y,t,full; //full is -1 if update
};
int ans[MN], bit[MN];
set<int> zeroes;
char s[10];
void update (int i, int v) {
	for (;i<MN;i+=i&-i)
		bit[i] += v;
}
int query (int i) {
	int ret = 0;
	for (;i;i^=i&-i)
		ret += bit[i];
	return ret;
}
void cdq (int l, int r, vector<Q> &queries) { //cdq over x
	if (queries.empty()) return;
	int mid = (l+r)/2;
	vector<Q> lq,rq;
	for (Q &q : queries) {
		if (q.full == -1) {
			if (q.x <= mid) update(q.y,q.t),lq.push_back(q);
			else rq.push_back(q);
		} else {
			if (q.x <= mid && l != r) lq.push_back(q);
			else ans[q.t] += query(q.y),rq.push_back(q);
		}
	}
	for (Q &q : lq) if (q.full==-1) update(q.y,-q.t);
	if (l<r) {
		cdq(l,mid,lq); cdq(mid+1,r,rq);
	}
}
int main () {
	int n,q; char c; int a,b;
	scanf ("%d %d",&n,&q);
	vector<Q> queries;
	zeroes.insert(0); zeroes.insert(n+1);
	for (int i = 1; i <= n; i++) {
		scanf (" %c",&c);
		if (c == '0') zeroes.insert(i);
	}
	for (int i = 1; i <= q; i++) {
		scanf (" %s %d",s,&a);
		if (s[0] == 'q') {
			scanf ("%d",&b); --b;
			if (*zeroes.lower_bound(a) > b) ans[i] = i;
			queries.push_back({a,b,i,0});
		} else {
			int cmpl = *prev(zeroes.lower_bound(a)) + 1;
			int cmpr = *zeroes.upper_bound(a) - 1;
			int sign = zeroes.count(a) ? -1 : 1;
			queries.push_back({cmpl,a,i*sign,-1});
			queries.push_back({cmpl,cmpr+1,i*-sign,-1});
			queries.push_back({a+1,a,i*-sign,-1});
			queries.push_back({a+1,cmpr+1,i*sign,-1});
			if (sign > 0) zeroes.insert(a);
			else zeroes.erase(a);
		}
	}
	cdq(1,n,queries);
	for (Q &qq : queries) if (!qq.full) printf ("%d\n",ans[qq.t]);
	return 0;
}
/*
turn into 1:
update cmpl <= l <= i, i <= r <= cmpr with -t
turn into 0:
update cmpl <= l <= i, i <= r <= cmpr with t
query is point query
bit of a special case if it is currently all 1s, need to add current time
transform with 2d diff array since point update range query is nicer
turn into 1:
update (cmpl,i) with -t
update (cmpl,cmpr+1) with t
update (i+1,i) with t
update(i+1,cmpr+1) with -t
turn into 0:
update (cmpl,i) with t
update (cmpl,cmpr+1) with -t
update (i+1,i) with -t
update(i+1,cmpr+1) with t
query:
find sum with l <= L, r <= R
also add t+1 if currently intact

seems like easy cdq bash
*/

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:52:8: 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:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf (" %c",&c);
   ~~~~~~^~~~~~~~~~
street_lamps.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf (" %s %d",s,&a);
   ~~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d",&b); --b;
    ~~~~~~^~~~~~~~~

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