oj.uz

답안 #16870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16870 2015-10-24T01:48:22 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 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 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);
        }
    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 97492 KB Output is correct
2 Correct 3 ms 97492 KB Output is correct
3 Correct 5 ms 97492 KB Output is correct
4 Correct 5 ms 97492 KB Output is correct
5 Correct 4 ms 97492 KB Output is correct
6 Correct 6 ms 97492 KB Output is correct
7 Correct 5 ms 97492 KB Output is correct
8 Correct 4 ms 97492 KB Output is correct
9 Correct 5 ms 97492 KB Output is correct
10 Correct 5 ms 97492 KB Output is correct
11 Correct 6 ms 97492 KB Output is correct
12 Correct 0 ms 97492 KB Output is correct
13 Correct 8 ms 97492 KB Output is correct
14 Correct 11 ms 97492 KB Output is correct
15 Correct 7 ms 97492 KB Output is correct
16 Correct 2 ms 97492 KB Output is correct
17 Correct 0 ms 97492 KB Output is correct
18 Correct 3 ms 97492 KB Output is correct
19 Correct 0 ms 97492 KB Output is correct
20 Correct 4 ms 97492 KB Output is correct
21 Correct 16 ms 97492 KB Output is correct
22 Correct 7 ms 97492 KB Output is correct
23 Correct 5 ms 97492 KB Output is correct
24 Correct 6 ms 97492 KB Output is correct

Subtask #2
0.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1237 ms 97492 KB Output is correct
2 Correct 818 ms 97624 KB Output is correct
3 Correct 1753 ms 97492 KB Output is correct
4 Correct 1557 ms 97756 KB Output is correct
5 Correct 943 ms 97888 KB Output is correct
6 Correct 700 ms 97888 KB Output is correct
7 Correct 913 ms 97888 KB Output is correct
8 Correct 944 ms 97888 KB Output is correct
9 Correct 1950 ms 98284 KB Output is correct
10 Correct 2128 ms 98284 KB Output is correct
11 Correct 1332 ms 98152 KB Output is correct
12 Execution timed out 3000 ms 97624 KB Program timed out