| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16868 |
2015-10-24T01:40:32 Z |
gs14004 |
통로 위의 개미 (kriii3_X) |
C++14 |
|
3000 ms |
92712 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline long long _readLong() {
int c, s;
lint x;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
lint l;
int q;
int ants_kth[200005];
struct node{
node *ls, *rs;
int v;
node(){
ls = rs = NULL;
v = 0;
}
};
void add(lint pos, lint ps, lint pe, node* p){
p->v++;
if(ps == pe) return;
lint pm = (ps + pe) / 2;
if(pos <= pm){
if(!p->ls) p->ls = new node();
add(pos, ps, pm, p->ls);
}
else{
if(!p->rs) p->rs = new node();
add(pos, pm + 1, pe, p->rs);
}
}
int sum(lint s, lint e, lint ps, lint pe, node* p){
if(s <= ps && pe <= e) return p->v;
lint pm = (ps + pe) / 2;
int ret = 0;
if(pm >= s && p->ls) ret += sum(s,e,ps,pm,p->ls);
if(e >= pm + 1 && p->rs) ret += sum(s,e,pm+1,pe,p->rs);
return ret;
}
node *root1, *root2;
inline int get_sum(lint s, lint e, node *r){
if(e >= 2 * l){
return sum(s, 2*l-1, 0, 2*l-1, r) + sum(0, e - 2*l, 0, 2*l-1, r);
}
return sum(s, e, 0, 2*l-1, r);
}
inline lint norm(lint x){
x %= 2 * l;
x += 2 * l;
x %= 2 * l;
return x;
}
int piv = 1;
int get_low(lint p, lint t){
if(p == l) return piv-1;
int ret = 0;
ret += get_sum(norm(-t), norm(-t) + p, root1);
ret += get_sum(norm(2 * l - p - t), norm(2 * l - p - t) + p - 1, root1);
ret += get_sum(norm(t), norm(t) + p, root2);
ret += get_sum(norm(2 * l - p + t), norm(2 * l - p + t) + p - 1, root2);
return ret;
}
deque<int> v[705];
int map_int[200005];
int main(){
v[0].push_back(-1);
root1 = new node();
root2 = new node();
l = _readLong();
q = _readInt();
for(int i=0; i<q; i++){
lint t = _readLong();
lint p = _readLong();
if(p == 1){
lint pos = _readLong();
lint dx = _readLong();
int k = 1 + get_low(pos,t);
map_int[piv] = k / 300;
v[k/300].push_back(-1);
for(int i=v[k/300].size() - 1; i > k % 300; i--){
v[k/300][i] = v[k/300][i-1];
}
v[k/300][k%300] = piv;
for(int i=k / 300; i <= piv / 300; i++){
if(v[i].size() <= 300) break;
if(v[i].size() > 300){
map_int[v[i].back()] = i+1;
v[i+1].push_front(v[i].back());
v[i].pop_back();
}
}
piv++;
lint p = 1ll * pos - (1ll * dx * t % (2 * l)) + 2 * l;
p %= (2 * l);
p += 2 * l;
p %= 2 * l;
if(dx < 0) add(p,0,2*l-1,root2);
else add(p,0,2*l-1,root1);
}
else{
int x = _readInt();
int pt = map_int[x];
for(int j=0; j<v[pt].size(); j++){
if(v[pt][j] == x){
x = pt * 300 + j;
break;
}
}
int s = 0, e = l;
while(s != e){
int m = (s+e)/2;
if(get_low(m,t) < x) s = m+1;
else e = m;
}
printf("%d\n",s);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4272 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3744 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4008 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3876 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4140 KB |
Output is correct |
| 6 |
Correct |
5 ms |
4140 KB |
Output is correct |
| 7 |
Correct |
5 ms |
4272 KB |
Output is correct |
| 8 |
Correct |
5 ms |
4140 KB |
Output is correct |
| 9 |
Correct |
6 ms |
4272 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4272 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3744 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4140 KB |
Output is correct |
| 13 |
Correct |
7 ms |
3876 KB |
Output is correct |
| 14 |
Correct |
7 ms |
4008 KB |
Output is correct |
| 15 |
Correct |
7 ms |
3744 KB |
Output is correct |
| 16 |
Correct |
0 ms |
3876 KB |
Output is correct |
| 17 |
Correct |
3 ms |
3876 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4140 KB |
Output is correct |
| 19 |
Correct |
4 ms |
4140 KB |
Output is correct |
| 20 |
Correct |
2 ms |
4140 KB |
Output is correct |
| 21 |
Correct |
15 ms |
3876 KB |
Output is correct |
| 22 |
Correct |
6 ms |
3744 KB |
Output is correct |
| 23 |
Correct |
5 ms |
3744 KB |
Output is correct |
| 24 |
Correct |
5 ms |
4008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1186 ms |
5856 KB |
Output is correct |
| 2 |
Correct |
865 ms |
9024 KB |
Output is correct |
| 3 |
Correct |
1721 ms |
5456 KB |
Output is correct |
| 4 |
Correct |
1643 ms |
8892 KB |
Output is correct |
| 5 |
Correct |
1084 ms |
35424 KB |
Output is correct |
| 6 |
Correct |
828 ms |
45852 KB |
Output is correct |
| 7 |
Correct |
1113 ms |
38456 KB |
Output is correct |
| 8 |
Correct |
1174 ms |
59568 KB |
Output is correct |
| 9 |
Correct |
2346 ms |
92688 KB |
Output is correct |
| 10 |
Correct |
2873 ms |
92712 KB |
Output is correct |
| 11 |
Correct |
1534 ms |
92184 KB |
Output is correct |
| 12 |
Execution timed out |
3000 ms |
29616 KB |
Program timed out |
