oj.uz

Submission #172174

# Submission time Handle Problem Language Result Execution time Memory
172174 2019-12-31T12:53:15 Z dennisstar Street Lamps (APIO19_street_lamps) C++11
60 / 100
 4848 ms 524292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
 
int R, C;
struct dty {
	dty *l, *r;
	int dt, L, R; int Key;
	int md;
	dty(int k) {Key=k; dt=0; l=r=NULL;}
	inline void upd(int y, int val, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) {
			if (Key==y) {dt+=val; return ;}
			if (Key<=md) { l=new dty(Key); l->dt=dt; }
			else { r=new dty(Key); r->dt=dt; }
			Key=0;
		}
		if (y<=md) {
			if (!l) l=new dty(y);
			l->upd(y, val, ys, md);
		}
		else {
			if (!r) r=new dty(y);
			r->upd(y, val, md+1, ye);
		}
		L=(l?l->dt:0);
		R=(r?r->dt:0);
		dt=L+R;
	}
	inline int get(int y1, int y2, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) return (y1<=Key&&Key<=y2)?dt:0;
		if (y1<=ys&&ye<=y2) return dt;
		L=R=0;
		if (!(md<y1)) L=(l?(l->get(y1, y2, ys, md)):0);
		if (md+1<=y2&&md+1<=ye) R=(r?r->get(y1, y2, md+1, ye):0);
		return L+R;
	}
	inline int get(int y, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) return (y==Key?dt:0);
		if (y<=md) return l?l->get(y, ys, md):0;
		else return r?r->get(y, md+1, ye):0;
	}
};

struct dtx {
	dty *seg;
	dtx *l, *r;
	int md;
	int L, R;
	dtx() {l=r=NULL; seg=NULL;}
	inline void upd(int x, int y, int val, int xs, int xe) {
		if (!seg) seg=new dty(y);
		if (xs==xe) {seg->upd(y, val, 1, C); return ;}
		md=(xs+xe)/2;
		if (x<=md) {
			if (!l) l=new dtx();
			l->upd(x, y, val, xs, md);
		}
		else {
			if (!r) r=new dtx();
			r->upd(x, y, val, md+1, xe);
		}
		seg->upd(y, val, 1, C);
	}
	inline int get(int x1, int y1, int x2, int y2, int xs, int xe) {
		if (!seg) return 0;
		if (x1<=xs&&xe<=x2) return seg->get(y1, y2, 1, C);
		md=(xs+xe)/2;
		L=R=0;
		if (x1<=md) L=(l?(l->get(x1, y1, x2, y2, xs, md)):0);
		if (md+1<=x2&&md+1<=xe) R=(r?(r->get(x1, y1, x2, y2, md+1, xe)):0);
		return L+R;
	}
};

dtx *root=new dtx();

int n, q;
char s[10]; int I, a, b;
int ar[300010];
set<pair<pii, int> > S;

int main() {
	scanf("%d %d", &n, &q);
	R=C=n;
	for (int i=1; i<=n; i++) scanf("%1d", &ar[i]);
	for (int i=1; i<=n; i++) {
		if (!ar[i]) continue;
		int j;
		for (j=i; j<=n; j++) if (!ar[j]) break;
		S.insert({make_pair(i, j-1), 0});
		i=j-1;
	}
	set<pair<pii, int> >::iterator it;
	pair<pii, int> pi, pi1, pi2;
	int ans;
	for (int i=1; i<=q; i++) {
		scanf("%s", s);
		if (s[0]=='t') {
			scanf("%d", &I);
			if (ar[I]) {
				it=S.upper_bound({make_pair(I, (1<<30)), (1<<30)});
				it--; pi=(*it); S.erase(it);
				root->upd(pi.fi.fi, pi.fi.se, i-pi.se, 1, R);
				if (pi.fi.fi<I) S.insert({make_pair(pi.fi.fi, I-1), i});
				if (pi.fi.se>I) S.insert({make_pair(I+1, pi.fi.se), i});
			}
			else {
				if (ar[I-1]) {
					it=S.upper_bound({make_pair(I-1, (1<<30)), (1<<30)});
					it--; pi1=(*it); S.erase(it);
					root->upd(pi1.fi.fi, pi1.fi.se, i-pi1.se, 1, R);
				}
				else pi1={make_pair(I, I), 0};
				if (ar[I+1]) {
					it=S.upper_bound({make_pair(I+1, (1<<30)), (1<<30)});
					it--; pi2=(*it); S.erase(it);
					root->upd(pi2.fi.fi, pi2.fi.se, i-pi2.se, 1, R);
				}
				else pi2={make_pair(I, I), 0};
				S.insert({make_pair(pi1.fi.fi, pi2.fi.se), i});
			}
			ar[I]=1-ar[I];
		}
		else {
			scanf("%d %d", &a, &b); b--;
			if (!S.size()) ans=0;
			else {
				it=S.upper_bound({make_pair(a, (1<<30)), (1<<30)});
				if (it==S.begin()) ans=0;
				else {
					it--;
					if ((*it).fi.fi<=a&&(*it).fi.se>=b) ans=i-(*it).se;
					else ans=0;
				}
			}
			ans+=root->get(1, b, a, C, 1, R);
			printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:96: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:98:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=n; i++) scanf("%1d", &ar[i]);
                           ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~
street_lamps.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &I);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &a, &b); b--;
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 4768 KB Output is correct
2 Correct 422 ms 5884 KB Output is correct
3 Correct 1220 ms 21884 KB Output is correct
4 Correct 3578 ms 332816 KB Output is correct
5 Correct 4108 ms 376796 KB Output is correct
6 Correct 3433 ms 377120 KB Output is correct
7 Correct 167 ms 8056 KB Output is correct
8 Correct 176 ms 9624 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1272 KB Output is correct
2 Correct 6 ms 1272 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Runtime error 4244 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 6 ms 1316 KB Output is correct
5 Correct 656 ms 21396 KB Output is correct
6 Correct 1864 ms 227496 KB Output is correct
7 Correct 3068 ms 376312 KB Output is correct
8 Correct 4848 ms 519500 KB Output is correct
9 Correct 453 ms 5256 KB Output is correct
10 Correct 303 ms 3588 KB Output is correct
11 Correct 460 ms 5264 KB Output is correct
12 Correct 311 ms 3748 KB Output is correct
13 Correct 456 ms 5380 KB Output is correct
14 Correct 309 ms 3732 KB Output is correct
15 Correct 165 ms 8056 KB Output is correct
16 Correct 175 ms 9464 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 297 ms 4768 KB Output is correct
9 Correct 422 ms 5884 KB Output is correct
10 Correct 1220 ms 21884 KB Output is correct
11 Correct 3578 ms 332816 KB Output is correct
12 Correct 4108 ms 376796 KB Output is correct
13 Correct 3433 ms 377120 KB Output is correct
14 Correct 167 ms 8056 KB Output is correct
15 Correct 176 ms 9624 KB Output is correct
16 Correct 6 ms 1272 KB Output is correct
17 Correct 6 ms 1272 KB Output is correct
18 Correct 5 ms 1016 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Runtime error 4244 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -