| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27273 |
2017-07-12T06:33:29 Z |
까제비(#1140) |
Ruka (COI15_ruka) |
C++14 |
|
2000 ms |
3836 KB |
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 1e5 + 1000, ROOT_N = 400;
pi operator+(const pi &a, const pi &b) { return pi(a.one+b.one, a.two+b.two); }
pi operator-(const pi &a, const pi &b) { return pi(a.one-b.one, a.two-b.two); }
int N, Q; vector<pi> Ps;
pi Sum[MAX_N / ROOT_N];
struct IDX {
int P; vector<int> val;
vector<int> Co;
IDX() {}
IDX(int n) {
for(P=1; P<n; P<<=1);
val = vector<int>(2*P, 0);
}
void setting(vector<int> co) {
sort(ALL(co)); co.erase(unique(ALL(co)), co.end());
Co = co;
for(int i=0; i<2*P; i++) val[i] = 0;
}
void update(int v, int p, int k) {
v = lower_bound(ALL(Co), v) - Co.begin() + p;
if(v >= SZ(Co)) return;
for(val[v+=P] += k; v>>=1; val[v] = val[v*2] + val[v*2+1]);
}
int getSum(int v) {
int ll = v;
v = lower_bound(ALL(Co), v) - Co.begin() - 1;
// printf("%d -> %dth\n", ll, v);
if(v < 0) return 0;
int a = 0, b = v, res = 0;
for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
if(a%2==1) res += val[a++];
if(b%2==0) res += val[b--];
}
return res;
}
};
IDX idx[2][MAX_N / ROOT_N];
void updateG(int i) {
pi now = pi(0, 0);
vector<int> co[2]; co[0].push_back(0), co[1].push_back(0);
for(int j=0, p=i*ROOT_N; p<N && j<ROOT_N; j++, p++) {
now = now + Ps[p];
co[0].push_back(now.one);
co[1].push_back(now.two);
}
idx[0][i].setting(co[0]);
idx[1][i].setting(co[1]);
// printf("setting well\n");
now = pi(0, 0);
for(int j=0, p=i*ROOT_N; p<N && j<ROOT_N; j++, p++) {
pi past = now;
now = now + Ps[p];
idx[0][i].update(min(past.one, now.one), 0, +1);
idx[0][i].update(max(past.one, now.one), 0, -1);
idx[1][i].update(min(past.two, now.two), 0, +1);
idx[1][i].update(max(past.two, now.two), 0, -1);
// printf("[%d %d] -> [%d %d]\n", past.one, past.two, now.one, now.two);
}
}
int main() {
cin >> N;
pi base = pi(1, 1);
for(int i=0; i<N; i++) {
int x, y; scanf("%d%d", &x, &y);
Ps.push_back(pi(x, y));
Sum[i / ROOT_N] = Sum[i / ROOT_N] + pi(x, y);
}
for(int i=0; i<=(N-1)/ROOT_N; i++) {
idx[0][i] = idx[1][i] = IDX(ROOT_N);
updateG(i);
}
cin >> Q;
int cur = 0;
while(Q--) {
char s[5]; scanf("%s", s);
if(s[0] == 'C') {
int x, y; scanf("%d%d", &x, &y);
int i = cur / ROOT_N;
Sum[i] = Sum[i] - Ps[cur];
Ps[cur] = pi(x, y);
Sum[i] = Sum[i] + Ps[cur];
updateG(i);
} else if(s[0] == 'F') {
cur = min(N-1, cur+1);
} else if(s[0] == 'B') {
cur = max(0, cur-1);
} else if(s[0] == 'Q') {
pi sum = base;
int ans = 0;
for(int i=0; i<=(N-1)/ROOT_N; i++) {
ans += idx[0][i].getSum(-sum.one);
ans += idx[1][i].getSum(-sum.two);
sum = sum + Sum[i];
}
printf("%d\n", ans);
}else assert(false);
}
return 0;
}
/*
struct IDX {
int P; vector<pi> val;
IDX() {}
IDX(int n) {
for(P=1; P<n; P<<=1);
val = vector<pi>(2*P);
}
void update(int v, pi p) {
for(val[v+=P] = p; v>>=1; val[v] = val[v*2] + val[v*2+1]);
}
pi getSum(int a, int b) {
pi res = pi(0, 0);
for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
if(a%2==1) res = res + val[a++];
if(b%2==0) res = res + val[b--];
}
return res;
}
};
*/
Compilation message
ruka.cpp: In member function 'int IDX::getSum(int)':
ruka.cpp:41:7: warning: unused variable 'll' [-Wunused-variable]
int ll = v;
^
ruka.cpp: In function 'int main()':
ruka.cpp:84:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
^
ruka.cpp:95:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char s[5]; scanf("%s", s);
^
ruka.cpp:97:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2056 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2056 KB |
Output is correct |
| 3 |
Correct |
109 ms |
2056 KB |
Output is correct |
| 4 |
Correct |
79 ms |
2056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2056 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2056 KB |
Output is correct |
| 3 |
Correct |
109 ms |
2056 KB |
Output is correct |
| 4 |
Correct |
79 ms |
2056 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
3836 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2056 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2056 KB |
Output is correct |
| 3 |
Correct |
109 ms |
2056 KB |
Output is correct |
| 4 |
Correct |
79 ms |
2056 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
3836 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
