Submission #16871

#	Time	Username	Problem	Language	Result	Execution time	Memory
16871		gs14004	통로 위의 개미 (kriii3_X)	C++14	30 / 85	3000 ms	98284 KiB

X

#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);
        }
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 55