Submission #16871

# Submission time Handle Problem Language Result Execution time Memory
16871 2015-10-24T01:50:14 Z gs14004 통로 위의 개미 (kriii3_X) C++14
30 / 85
3000 ms 98284 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{
    int ls, rs, v;
};

node tree[8000005];
int piv = 2;
   
void add(int pos, int ps, int pe, int p){
    tree[p].v++;
    if(ps == pe) return;
    int pm = ps + (pe - ps) / 2;
    if(pos <= pm){
        if(!tree[p].ls) tree[p].ls = ++piv;
        add(pos, ps, pm, tree[p].ls);
    }
    else{
        if(!tree[p].rs) tree[p].rs = ++piv;
        add(pos, pm + 1, pe, tree[p].rs);
    }
}
   
int sum(int s, int e, int ps, int pe, int p){
    if(s <= ps && pe <= e) return tree[p].v;
    int pm = ps + (pe - ps) / 2;
    int ret = 0;
    if(pm >= s && tree[p].ls) ret += sum(s,e,ps,pm,tree[p].ls);
    if(e >= pm + 1 && tree[p].rs) ret += sum(s,e,pm+1,pe,tree[p].rs);
    return ret;
}
      
inline int get_sum(lint s, lint e, int r){
    if(e >= 2 * l){
    	return tree[r].v - sum(e - 2 * l + 1, s - 1, 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 qiv = 1;
   
int get_low(lint p, lint t){
    if(p == l) return qiv-1;
    int ret = 0;
    ret += get_sum(norm(-t), norm(-t) + p, 1);
    ret += get_sum(norm(- p - t), norm(- p - t) + p - 1, 1);
    ret += get_sum(norm(t), norm(t) + p, 2);
    ret += get_sum(norm(- p + t), norm(- p + t) + p - 1, 2);
    return ret;
}
   
deque<int> v[705];
int map_int[200005];
  
int main(){
    v[0].push_back(-1);
    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[qiv] = 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] = qiv;
            for(int i=k / 300; i <= qiv / 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();
                }
            }
            qiv++;
            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,2);
            else add(p,0,2*l-1,1);
        }
        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 6 ms 97492 KB Output is correct
2 Correct 0 ms 97492 KB Output is correct
3 Correct 5 ms 97492 KB Output is correct
4 Correct 3 ms 97492 KB Output is correct
5 Correct 3 ms 97492 KB Output is correct
6 Correct 4 ms 97492 KB Output is correct
7 Correct 4 ms 97492 KB Output is correct
8 Correct 6 ms 97492 KB Output is correct
9 Correct 4 ms 97492 KB Output is correct
10 Correct 6 ms 97492 KB Output is correct
11 Correct 6 ms 97492 KB Output is correct
12 Correct 2 ms 97492 KB Output is correct
13 Correct 5 ms 97492 KB Output is correct
14 Correct 11 ms 97492 KB Output is correct
15 Correct 6 ms 97492 KB Output is correct
16 Correct 4 ms 97492 KB Output is correct
17 Correct 4 ms 97492 KB Output is correct
18 Correct 2 ms 97492 KB Output is correct
19 Correct 2 ms 97492 KB Output is correct
20 Correct 2 ms 97492 KB Output is correct
21 Correct 15 ms 97492 KB Output is correct
22 Correct 6 ms 97492 KB Output is correct
23 Correct 2 ms 97492 KB Output is correct
24 Correct 2 ms 97492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1246 ms 97492 KB Output is correct
2 Correct 821 ms 97624 KB Output is correct
3 Correct 1774 ms 97492 KB Output is correct
4 Correct 1557 ms 97756 KB Output is correct
5 Correct 946 ms 97888 KB Output is correct
6 Correct 679 ms 97888 KB Output is correct
7 Correct 919 ms 97888 KB Output is correct
8 Correct 947 ms 97888 KB Output is correct
9 Correct 1890 ms 98284 KB Output is correct
10 Correct 2110 ms 98284 KB Output is correct
11 Correct 1352 ms 98152 KB Output is correct
12 Execution timed out 3000 ms 97624 KB Program timed out