oj.uz

Submission #15567

# Submission time Handle Problem Language Result Execution time Memory
15567 2015-07-12T23:53:58 Z gs14004 통로 위의 개미 (kriii3_X) C++14
30 / 85
 3000 ms 92560 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long lint;
 
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(e < ps || pe < s) return 0;
    if(s <= ps && pe <= e) return p->v;;
    lint pm = (ps + pe) / 2;
    int ret = 0;
    if(p->ls) ret += sum(s,e,ps,pm,p->ls);
    if(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();
    scanf("%lld %d",&l,&q);
    for(int i=0; i<q; i++){
        lint t;
        lint p;
        scanf("%lld %lld",&t,&p);
        if(p == 1){
            lint pos, dx;
            scanf("%lld %lld",&pos, &dx);
            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;
            scanf("%d",&x);
            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);
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4120 KB Output is correct
2 Correct 5 ms 3592 KB Output is correct
3 Correct 5 ms 3856 KB Output is correct
4 Correct 5 ms 3724 KB Output is correct
5 Correct 5 ms 3988 KB Output is correct
6 Correct 5 ms 3988 KB Output is correct
7 Correct 7 ms 4120 KB Output is correct
8 Correct 4 ms 3988 KB Output is correct
9 Correct 7 ms 4120 KB Output is correct
10 Correct 7 ms 4120 KB Output is correct
11 Correct 3 ms 3592 KB Output is correct
12 Correct 5 ms 3988 KB Output is correct
13 Correct 7 ms 3724 KB Output is correct
14 Correct 13 ms 3856 KB Output is correct
15 Correct 8 ms 3592 KB Output is correct
16 Correct 4 ms 3724 KB Output is correct
17 Correct 4 ms 3724 KB Output is correct
18 Correct 0 ms 3988 KB Output is correct
19 Correct 4 ms 3988 KB Output is correct
20 Correct 5 ms 3988 KB Output is correct
21 Correct 17 ms 3724 KB Output is correct
22 Correct 8 ms 3592 KB Output is correct
23 Correct 6 ms 3592 KB Output is correct
24 Correct 3 ms 3856 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1406 ms 5704 KB Output is correct
2 Correct 1022 ms 8872 KB Output is correct
3 Correct 2043 ms 5304 KB Output is correct
4 Correct 1983 ms 8740 KB Output is correct
5 Correct 1197 ms 35272 KB Output is correct
6 Correct 1006 ms 45700 KB Output is correct
7 Correct 1296 ms 38304 KB Output is correct
8 Correct 1298 ms 59416 KB Output is correct
9 Correct 2645 ms 92536 KB Output is correct
10 Execution timed out 3000 ms 92560 KB Program timed out
11 Halted 0 ms 0 KB -