| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27297 |
2017-07-12T07:23:53 Z |
알렉스(#1147) |
Ruka (COI15_ruka) |
C++14 |
|
449 ms |
28364 KB |
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <tuple>
#include <set>
using namespace std;
inline void add(int idt[], int bp, int x, int y, int v)
{
if(y < x)
swap(x, y);
x += bp;
y += bp;
while(x < y)
{
if(x % 2 == 1)
{
idt[x] += v;
x++;
}
if(y % 2 == 0)
{
idt[y] += v;
y--;
}
x /= 2;
y /= 2;
}
if(x == y)
idt[x] += v;
}
inline int cnt(int idt[], int bp, int x)
{
int r = 0;
x += bp;
while(x)
{
r += idt[x];
x /= 2;
}
return r;
}
int arr[100000];
char que[300000];
vector<int> nex;
vector<int> res;
int n, m;
vector<int> com1;
vector<int> com2;
int tmp[100000];
int idt1[2100000];
int idt2[2100000];
inline int idx(vector<int> &com, int x)
{
return lower_bound(com.begin(), com.end(), x) - com.begin();
}
void process()
{
com1.clear();
com2.clear();
res.clear();
memset(idt1, 0, sizeof idt1);
memset(idt2, 0, sizeof idt2);
int p, off, np, cur, t, i;
int bp1, bp2;
for(i = 0; i<n; i++)
tmp[i] = arr[i];
p = 1;
off = 0;
np = 0;
cur = 0;
t = p + tmp[0];
for(i = 1; i<n; i++)
{
com2.push_back(t);
com2.push_back(t+tmp[i]);
t += tmp[i];
}
for(i = 0; i<m; i++)
{
if(que[i] == 'B')
{
if(cur == 0)
continue;
com2.push_back(p-off);
com2.push_back(p+tmp[cur]-off);
cur--;
p -= tmp[cur];
com1.push_back(p);
com1.push_back(p+tmp[cur]);
}
else if(que[i] == 'F')
{
if(cur == n-1)
continue;
com1.push_back(p);
com1.push_back(p+tmp[cur]);
p += tmp[cur];
cur++;
com2.push_back(p-off);
com2.push_back(p+tmp[cur]-off);
}
else if(que[i] == 'C')
{
if(i != m-1 && que[i+1] == 'C')
{
np++;
continue;
}
off += nex[np] - tmp[cur];
tmp[cur] = nex[np++];
}
else
{
com1.push_back(0);
com2.push_back(-off);
}
}
sort(com1.begin(), com1.end());
com1.erase(unique(com1.begin(), com1.end()), com1.end());
sort(com2.begin(), com2.end());
com2.erase(unique(com2.begin(), com2.end()), com2.end());
for(bp1 = 1; bp1 <= com1.size(); bp1 *= 2);
for(bp2 = 1; bp2 <= com2.size(); bp2 *= 2);
p = 1;
off = 0;
np = 0;
cur = 0;
t = p + arr[0];
for(i = 1; i<n; i++)
{
add(idt2, bp2, idx(com2, t), idx(com2, t+arr[i]), 1);
t += arr[i];
}
for(i = 0; i<m; i++)
{
if(que[i] == 'B')
{
if(cur == 0)
continue;
add(idt2, bp2, idx(com2, p-off), idx(com2, p+arr[cur]-off), 1);
cur--;
p -= arr[cur];
add(idt1, bp1, idx(com1, p), idx(com1, p+arr[cur]), -1);
}
else if(que[i] == 'F')
{
if(cur == n-1)
continue;
add(idt1, bp1, idx(com1, p), idx(com1, p+arr[cur]), 1);
p += arr[cur];
cur++;
add(idt2, bp2, idx(com2, p-off), idx(com2, p+arr[cur]-off), -1);
}
else if(que[i] == 'C')
{
if(i != m-1 && que[i+1] == 'C')
{
np++;
continue;
}
off += nex[np] - arr[cur];
arr[cur] = nex[np++];
}
else
{
t = cnt(idt1, bp1, idx(com1, 0)) + cnt(idt2, bp2, idx(com2, -off));
if(p<0 && p+arr[cur]>0 || p>0 && p+arr[cur]<0)
t++;
res.push_back(t);
}
}
}
int t_arr[100000];
vector<int> t_nex;
vector<int> t_res;
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
int x, i;
scanf("%d", &n);
for(i = 0; i<n; i++)
scanf("%d%d", &arr[i], &t_arr[i]);
scanf("%d", &m);
for(i = 0; i<m; i++)
{
scanf(" %c", &que[i]);
if(que[i] == 'C')
{
scanf("%d", &x);
nex.push_back(x);
scanf("%d", &x);
t_nex.push_back(x);
}
}
process();
for(i = 0; i<n; i++)
arr[i] = t_arr[i];
for(i = 0; i<nex.size(); i++)
nex[i] = t_nex[i];
swap(res, t_res);
process();
for(i = 0; i<res.size(); i++)
printf("%d\n", res[i] + t_res[i]);
return 0;
}
Compilation message
ruka.cpp: In function 'void process()':
ruka.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(bp1 = 1; bp1 <= com1.size(); bp1 *= 2);
^
ruka.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(bp2 = 1; bp2 <= com2.size(); bp2 *= 2);
^
ruka.cpp:197:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(p<0 && p+arr[cur]>0 || p>0 && p+arr[cur]<0)
^
ruka.cpp: In function 'int main()':
ruka.cpp:235:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i<nex.size(); i++)
^
ruka.cpp:241:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i<res.size(); i++)
^
ruka.cpp:215:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
ruka.cpp:217:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &arr[i], &t_arr[i]);
^
ruka.cpp:218:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
^
ruka.cpp:221:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &que[i]);
^
ruka.cpp:224:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
ruka.cpp:226:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19052 KB |
Output is correct |
| 2 |
Correct |
6 ms |
19052 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19052 KB |
Output is correct |
| 4 |
Correct |
6 ms |
19052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19052 KB |
Output is correct |
| 2 |
Correct |
6 ms |
19052 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19052 KB |
Output is correct |
| 4 |
Correct |
6 ms |
19052 KB |
Output is correct |
| 5 |
Correct |
136 ms |
21696 KB |
Output is correct |
| 6 |
Correct |
79 ms |
21448 KB |
Output is correct |
| 7 |
Correct |
126 ms |
21700 KB |
Output is correct |
| 8 |
Correct |
113 ms |
21700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19052 KB |
Output is correct |
| 2 |
Correct |
6 ms |
19052 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19052 KB |
Output is correct |
| 4 |
Correct |
6 ms |
19052 KB |
Output is correct |
| 5 |
Correct |
136 ms |
21696 KB |
Output is correct |
| 6 |
Correct |
79 ms |
21448 KB |
Output is correct |
| 7 |
Correct |
126 ms |
21700 KB |
Output is correct |
| 8 |
Correct |
113 ms |
21700 KB |
Output is correct |
| 9 |
Correct |
319 ms |
25800 KB |
Output is correct |
| 10 |
Correct |
449 ms |
28364 KB |
Output is correct |
| 11 |
Correct |
353 ms |
26312 KB |
Output is correct |
| 12 |
Correct |
379 ms |
26312 KB |
Output is correct |
