Submission #391102

#	Time	Username	Problem	Language	Result	Execution time	Memory
391102		nafis_shifat	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1177 ms	24908 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 BIT
{
	int bit[mxn] = {};
	void update(int p,int v) {
		if(p==0) return;
		for(;p< mxn; p+= p&-p) bit[p] += v;
	}
    int query(int p) {
    	int r=0;
    	for(;p>0;p-=p&-p) r += bit[p];
        return r;
    }
    int query(int a,int b) {
    	return query(b) - query(a - 1);
    }
} bt1,bt2;

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;
			bt1.update(Qs[i.s].r,Qs[i.s].val);
			bt2.update(Qs[i.s].i,Qs[i.s].val);
		}
		if(i.f.s == 2) {
			cursum -= Qs[i.s].val;
			bt1.update(Qs[i.s].r,-Qs[i.s].val);
			bt2.update(Qs[i.s].i,-Qs[i.s].val);
		}

		if(i.f.s == 0) {
			int x = bt1.query(Qs[i.s].r - 1);
			int y = bt2.query(mxn - 1) - bt2.query(Qs[i.s].r);
			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';
	}


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

	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.update(x,1);
			int lo = 1;
			int hi = x;

			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(cur.query(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(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.update(x,-1);
			}
			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(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]);
	}



	
}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:87:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |  int mid = l + r >> 1;
      |            ~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:145:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
street_lamps.cpp:161:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
street_lamps.cpp:194:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<QUERY>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |  for(int i = 0; i < Qs.size(); i++) {
      |                 ~~^~~~~~~~~~~
street_lamps.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |   scanf("%s",p);
      |   ~~~~~^~~~~~~~
street_lamps.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~
street_lamps.cpp:183:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  183 |    scanf("%d%d",&a,&b);
      |    ~~~~~^~~~~~~~~~~~~~

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