Submission #391088

#	Time	Username	Problem	Language	Result	Execution time	Memory
391088		nafis_shifat	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	642 ms	23704 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];

ll 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<QUERY> left,vector<QUERY> right) {
	vector<pair<pii,int>> v;

	for(int i = 0; i < left.size(); i++) {
		v.push_back(mp(mp(left[i].l,-1),i));
		v.push_back(mp(mp(left[i].i,2),i));
	}

	for(int i = 0; i < right.size(); i++) {
		v.push_back(mp(mp(right[i].l,0),i));
		//v.emplace_back(right[i].r,1,i);
	}

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

	ll cursum = 0;

	for(auto i : v) {
		if(i.f.s == -1) {
			//cout<<left[i.s].l<<" -- "<<left[i.s].r<<" -- "<<left[i.s].i<<endl;
			cursum += left[i.s].val;
			st1.update(1,1,n,left[i.s].r,left[i.s].val);
			st2.update(1,1,n,left[i.s].i,left[i.s].val);
		}
		if(i.f.s == 2) {
			cursum -= left[i.s].val;
			st1.update(1,1,n,left[i.s].r,-left[i.s].val);
			st2.update(1,1,n,left[i.s].i,-left[i.s].val);
		}

		if(i.f.s == 0) {
			ll x = st1.query(1,1,n,1,right[i.s].r - 1);
			ll y = st2.query(1,1,n,right[i.s].r + 1,n);
			//cout<<cursum<<" "<<x<<" "<<y<<" "<<right[i.s].r<<endl;

			ans[right[i.s].ind] += cursum - x - y;
		}
	}



}





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;
	vector<QUERY> left,right;

	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);
			left.push_back(q);
			
		} else {
			int a,b;
			scanf("%d%d",&a,&b);
			//Qs.push_back(QUERY(a,b,i));
			right.push_back(QUERY(a,b,i));

			if(cur.query(1,1,n,a,b) == b - a + 1) {
				ans[i] = i;
			}
		}
	}

	process(left,right);


	for(auto i : right) {
		cout<<ans[i.ind]<<endl;
	}



	
}

Compilation message (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 process(std::vector<QUERY>, std::vector<QUERY>)':
street_lamps.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<QUERY>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0; i < left.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
street_lamps.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<QUERY>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < right.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:150:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
street_lamps.cpp:166:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
street_lamps.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  139 |   scanf("%s",p);
      |   ~~~~~^~~~~~~~
street_lamps.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~
street_lamps.cpp:192:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  192 |    scanf("%d%d",&a,&b);
      |    ~~~~~^~~~~~~~~~~~~~

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