oj.uz

Submission #611467

# Submission time Handle Problem Language Result Execution time Memory
611467 2022-07-29T05:12:18 Z 반딧불(#8497) Segway (COI19_segway) C++17
40 / 100
 1000 ms 2000 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int num, pos, t, accel;
    dat(){}
    dat(int num, int pos, int t, int accel): num(num), pos(pos), t(t), accel(accel){}
    bool operator<(const dat &r)const{
        if(t!=r.t) return t>r.t;
        return pos<r.pos;
    }
};

struct Fenwiwck{
    const int n = 600;
    int tree[602];

    void init(){
        for(int i=0; i<=n; i++) tree[i] = 0;
    }

    void add(int x, int v){
        if(!x) return;
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        return sum(r) - sum(l-1);
    }
} tree;

int n, k;
int speed[20002][3];
bool accel[302];
int ans[20002];
int pos[20002];

priority_queue<dat> pq;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) for(int j=0; j<3; j++) scanf("%d", &speed[i][j]);
    scanf("%d", &k);
    for(int i=1; i<=k; i++){
        int x;
        scanf("%d", &x);
        accel[x] = 1;
    }
    tree.init();

    for(int i=1; i<=n; i++){
        pos[i] = 0;
        pq.push(dat(i, 0, 0, 0));
        tree.add(pos[i]*2, 1);
    }
    while(!pq.empty()){
        int nowT = pq.top().t;
        vector<dat> vec;
        while(!pq.empty() && pq.top().t == nowT){
            vec.push_back(pq.top()), pq.pop();
            dat tmp = vec.back();
            if(nowT){
                tree.add(tmp.pos * 2 - 1, -1);
                pos[tmp.num] = tmp.pos;
                tree.add(tmp.pos * 2, 1);
            }
        }

        vector<dat> nextVec;
        for(dat p: vec){
            int x = p.num, loc = p.pos, acc = p.accel, t = p.t;
//            printf("(%d %d %d %d)\n", x, loc, acc, t);
            if(loc==300){
                ans[x] = t;
                continue;
            }

            int nextSpeed, nextAcc;
            if(acc) nextSpeed = 1, nextAcc = acc-1;
            else if(accel[loc]){
                int tmp = tree.sum(loc*2+1, 600) % 20;
                if(tmp) nextSpeed = 1, nextAcc = tmp-1;
                else nextAcc = 0, nextSpeed = (loc<100 ? speed[x][0] : loc<200 ? speed[x][1] : speed[x][2]);
            }
            else nextAcc = 0, nextSpeed = (loc<100 ? speed[x][0] : loc<200 ? speed[x][1] : speed[x][2]);
            nextVec.push_back(dat(x, loc+1, t+nextSpeed, nextAcc));
        }

        for(dat p: nextVec){
            tree.add(p.pos * 2 - 2, -1);
            tree.add(p.pos * 2 - 1, 1);
            pq.push(p);
        }
    }

    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
segway.cpp:57:57: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     for(int i=1; i<=n; i++) for(int j=0; j<3; j++) scanf("%d", &speed[i][j]);
      |                                                    ~~~~~^~~~~~~~~~~~~~~~~~~~
segway.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
segway.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 34 ms 388 KB Output is correct
4 Correct 129 ms 580 KB Output is correct
5 Execution timed out 1012 ms 2000 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 3 ms 312 KB Output is correct
6 Correct 4 ms 316 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 9 ms 316 KB Output is correct
9 Correct 10 ms 340 KB Output is correct
10 Correct 15 ms 364 KB Output is correct
11 Correct 11 ms 340 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 34 ms 388 KB Output is correct
4 Correct 129 ms 580 KB Output is correct
5 Execution timed out 1012 ms 2000 KB Time limit exceeded
6 Halted 0 ms 0 KB -