제출 #391100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391100		nafis_shifat	가로등 (APIO19_street_lamps)	C++14	40 / 100	5069 ms	33980 KiB

street_lamps

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
const int mxn=3e5+5;
const int inf=1e9;
int a[mxn];

int ans[mxn] = {};
int n;
struct segtree {
	int tree[4 * mxn + 1];

	void Set(int node,int b,int e,int p,int v) {
		if(e < p || b > p)return;
		if(b == e) {
			tree[node] = v;
			return;
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		Set(left,b,mid,p,v);
		Set(right,mid+1,e,p,v);
		tree[node] = tree[left] + tree[right];
	}

	void update(int node,int b,int e,int p,int v) {
		if(e < p || b > p)return;
		if(b == e) {
			tree[node]+=v;
			return;
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		update(left,b,mid,p,v);
		update(right,mid+1,e,p,v);
		tree[node] = tree[left] + tree[right];
	}

	int query(int node,int b,int e,int l,int r) {
		if(e < l || b > r) return 0;
		if(b >= l && e <= r) {
			return tree[node];
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		return query(left,b,mid,l,r) + query(right,mid+1,e,l,r);
	}
} st1,st2;


struct QUERY {
	int l,r,ind,i;
	int val;
	QUERY(int a = 0,int b = 0,int c = 0,int d = -1 ,int v = 0) : l(a),r(b),ind(c),i(d),val(v) {}	
};
vector<QUERY> Qs;




void process(vector<int> left,vector<int> right) {
	vector<pair<pii,int>> v;

	for(int i : left) {
		v.push_back(mp(mp(Qs[i].l,-1),i));
		v.push_back(mp(mp(Qs[i].i,2),i));
	}

	for(int i : right) {
		v.push_back(mp(mp(Qs[i].l,0),i));
		//v.emplace_back(right[i].r,1,i);
	}

	sort(v.begin(),v.end());

	int cursum = 0;

	for(auto i : v) {
		if(i.f.s == -1) {
			cursum += Qs[i.s].val;
			st1.update(1,1,n,Qs[i.s].r,Qs[i.s].val);
			st2.update(1,1,n,Qs[i.s].i,Qs[i.s].val);
		}
		if(i.f.s == 2) {
			cursum -= Qs[i.s].val;
			st1.update(1,1,n,Qs[i.s].r,-Qs[i.s].val);
			st2.update(1,1,n,Qs[i.s].i,-Qs[i.s].val);
		}

		if(i.f.s == 0) {
			int x = st1.query(1,1,n,1,Qs[i.s].r - 1);
			int y = st2.query(1,1,n,Qs[i.s].r + 1,n);
			ans[Qs[i.s].ind] += cursum - x - y;
		}
	}



}



void solve(int l,int r) {

	if(l == r) return;
	int mid = l + r >> 1;

	vector<int> left,right;

	for(int i = l; i <= mid; i++) {
		if(Qs[i].i != -1) {
			left.push_back(i);
		}
	}

	for(int i = mid + 1; i <= r; i++) {
		if(Qs[i].i == -1) {
			right.push_back(i);
		}
	}

	process(left,right);

	solve(l,mid);
	solve(mid + 1,r);



}



int main() {
	int k;
	cin >> n >> k;

	string s;
	cin >> s;

	for(int i = 1; i <= n; i++) {
		a[i] = s[i - 1] - '0';
	}


	segtree cur;
	for(int i = 1; i <= n; i++) {
		cur.update(1,1,n,i,a[i]);
	}

	char p[7];

	for(int i = 1; i <= k; i++) {
		scanf("%s",p);
		if(p[0] == 't') {
			int x;
			scanf("%d",&x);
			QUERY q;
			if(a[x] == 0) 
				cur.Set(1,1,n,x,1);
			int lo = 1;
			int hi = x;

			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(cur.query(1,1,n,mid,x) == x - mid + 1) {
					q.l = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}




			lo = x;
			hi = n;

			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(cur.query(1,1,n,x,mid) == mid - x + 1) {
					q.r = mid;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}

			}
			q.ind = i;
			q.i = x;

			if(a[x] == 0) q.val = -i;
			else q.val = i;

			if(a[x] == 1) {
				cur.Set(1,1,n,x,0);
			}
			a[x] ^= 1;
			Qs.push_back(q);			
		} else {
			int a,b;
			scanf("%d%d",&a,&b);
			b--;
			Qs.push_back(QUERY(a,b,i));
			if(cur.query(1,1,n,a,b) == b - a + 1) {
				ans[i] = i;
			}
		}
	}

	solve(0,Qs.size() - 1);

	for(int i = 0; i < Qs.size(); i++) {
		if(Qs[i].i == -1) printf("%d\n",ans[Qs[i].ind]);
	}



	
}

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

street_lamps.cpp: In member function 'void segtree::Set(int, int, int, int, int)':
street_lamps.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid=b+e>>1;
      |           ~^~
street_lamps.cpp: In member function 'void segtree::update(int, int, int, int, int)':
street_lamps.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid=b+e>>1;
      |           ~^~
street_lamps.cpp: In member function 'int segtree::query(int, int, int, int, int)':
street_lamps.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=b+e>>1;
      |           ~^~
street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:115:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |  int mid = l + r >> 1;
      |            ~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:173:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  173 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
street_lamps.cpp:189:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  189 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
street_lamps.cpp:222:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<QUERY>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |  for(int i = 0; i < Qs.size(); i++) {
      |                 ~~^~~~~~~~~~~
street_lamps.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |   scanf("%s",p);
      |   ~~~~~^~~~~~~~
street_lamps.cpp:165:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  165 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~
street_lamps.cpp:211:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  211 |    scanf("%d%d",&a,&b);
      |    ~~~~~^~~~~~~~~~~~~~

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