oj.uz

답안 #391094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391094 2021-04-17T20:24:53 Z nafis_shifat 가로등 (APIO19_street_lamps) C++14
20 / 100
 3095 ms 43496 KB 
#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);
			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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 626 ms 23636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 997 ms 42928 KB Output is correct
6 Correct 1630 ms 40644 KB Output is correct
7 Correct 2275 ms 40712 KB Output is correct
8 Correct 3095 ms 43496 KB Output is correct
9 Correct 804 ms 25504 KB Output is correct
10 Correct 550 ms 33492 KB Output is correct
11 Correct 788 ms 25548 KB Output is correct
12 Correct 544 ms 33584 KB Output is correct
13 Correct 790 ms 25572 KB Output is correct
14 Correct 538 ms 33484 KB Output is correct
15 Correct 961 ms 35520 KB Output is correct
16 Correct 964 ms 35580 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -