Submission #27401

#	Time	Username	Problem	Language	Result	Execution time	Memory
27401		tlwpdus	Ruka (COI15_ruka)	C++11	100 / 100	1186 ms	9332 KiB

ruka

#include <bits/stdc++.h>
using namespace std;

int n, m, MAXN = 1e8+2, bia = 5e7+1;
struct BIT {
	unordered_map<int,int> bit;
	void upd(int idx, int val) {
		idx += bia;
		while(idx<=MAXN) {
			if (bit.find(idx)==bit.end()) bit[idx] = val;
			else bit.find(idx)->second += val;
			idx += idx&(-idx);
		}
	}
	int getv(int idx) {
		int res = 0;
		idx += bia;
		while(idx>0) {
			res += (bit.find(idx)==bit.end())?0:bit[idx];
			idx -= idx&(-idx);
		}
		return res;
	}
};

struct bs {
	BIT bitu, bitd;
	int arr[100100];
	int cur, sum, b;
	bs() {cur=b=0;sum=1;}
	void init() {
		int i, res = 1+arr[0];
		for (i=1;i<n;i++) {
			int p = res, q = res+arr[i];
			if (p>q) swap(p,q);
			bitd.upd(p,1);
			bitd.upd(q,-1);
			res += arr[i];
		}
	}
	void B() {
		if (!cur) return;
		int p = sum+b, q = sum+arr[cur]+b;
		if (p>q) swap(p,q);
		bitd.upd(p,1); bitd.upd(q,-1);
		cur--; sum -= arr[cur];
		p = sum; q = sum+arr[cur];
		if (p>q) swap(p,q);
		bitu.upd(p,-1); bitu.upd(q,1);
	}
	void F() {
		if (cur==n-1) return;
		int p = sum, q = sum+arr[cur];
		if (p>q) swap(p,q);
		bitu.upd(p,1); bitu.upd(q,-1);
		sum += arr[cur]; cur++;
		p = sum+b; q = sum+arr[cur]+b;
		if (p>q) swap(p,q);
		bitd.upd(p,-1); bitd.upd(q,1);
	}
	int Q() {
		return bitu.getv(0)+bitd.getv(b)+(1LL*sum*(sum+arr[cur])<0);
	}
	void C(int nx) {
		b += arr[cur]-nx;
		arr[cur] = nx;
	}
} x, y;

int main(){
	int i;

	scanf("%d",&n);
	for (i=0;i<n;i++) scanf("%d%d",&x.arr[i],&y.arr[i]);
	x.init(); y.init();
	scanf("%d",&m);
	for (i=0;i<m;i++) {
		char ch;
		scanf(" %c",&ch);
		if (ch=='B') {
			x.B(); y.B();
		}
		else if (ch=='F') {
			x.F(); y.F();
		}
		else if (ch=='Q') {
			printf("%d\n",x.Q()+y.Q());
		}
		else {
			int a, b;
			scanf("%d%d",&a,&b);
			x.C(a); y.C(b);
		}
	}

	return 0;
}

Compilation message (stderr)

ruka.cpp: In function 'int main()':
ruka.cpp:73:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
ruka.cpp:74:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;i<n;i++) scanf("%d%d",&x.arr[i],&y.arr[i]);
                                                     ^
ruka.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
ruka.cpp:79:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&ch);
                   ^
ruka.cpp:91:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&a,&b);
                       ^

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56