제출 #172173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172173		dennisstar	가로등 (APIO19_street_lamps)	C++11	0 / 100	4860 ms	519312 KiB

street_lamps

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20