oj.uz

Submission #585616

# Submission time Handle Problem Language Result Execution time Memory
585616 2022-06-29T06:27:51 Z 반딧불(#8385) MP3 Player (CEOI10_mp3player) C++17
100 / 100
 171 ms 11592 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Node{
    ll ax, ay, bx, by;
    Node(){}
    Node(ll ax, ll ay, ll bx, ll by): ax(ax), ay(ay), bx(bx), by(by){
        assert(ax-ay==bx-by);
    }

    ll calc(ll x){
        if(x<=ax) return ay;
        if(x>=bx) return by;
        return by-(bx-x);
    }

    Node operator+(Node &r){
        if(by <= r.ax) return Node(0, r.ay, 0, r.ay);
        else if(r.bx <= ay) return Node(0, r.by, 0, r.by);
        else if(ay <= r.ax && by <= r.bx) return Node(ax + (r.ax - ay), r.ay, bx, r.calc(by));
        else if(r.ax <= ay && r.bx <= by) return Node(ax, r.calc(ay), bx - (by - r.bx), r.by);
        else if(r.ax <= ay && by <= r.bx) return Node(ax, r.calc(ay), bx, r.calc(by));
        else return Node(ax + (r.ax - ay), r.ay, bx - (by - r.bx), r.by);
    }
};

struct segTree{
    Node tree[400002];

    void init(int i, int l, int r, Node node){
        tree[i] = node;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m, node);
        init(i*2+1, m+1, r, node);
    }

    void update(int i, int l, int r, int x, Node node){
        if(l==r){
            tree[i] = node;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, node);
        else update(i*2+1, m+1, r, x, node);
        tree[i] = tree[i*2] + tree[i*2+1];
    }
} tree;

int n; ll k, goal;
bool op[100002];
ll arr[100002];
vector<pair<ll, int> > vec;
ll ans, ansV;

int main(){
    scanf("%d %lld %lld", &n, &k, &goal);
    ansV = goal;
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c %lld", &c, &arr[i]);
        if(c == '+') op[i] = 1;
    }
    tree.init(1, 1, n, Node(0, 0, k, k));
    for(int i=1; i<n; i++) vec.push_back(make_pair(arr[i+1]-arr[i], i+1));
    sort(vec.begin(), vec.end());
    for(int i=0; i<(int)vec.size(); i++){
        int j = i;
        while(j < (int)vec.size()-1 && vec[j+1].first == vec[i].first) j++;
        for(int x=i; x<=j; x++){
            tree.update(1, 1, n, vec[x].second, op[vec[x].second] ? Node(0, 1, k-1, k) : Node(1, 0, k, k-1));
        }
        Node tmp = tree.tree[1];
        if(goal < tmp.ay || tmp.by < goal) continue;
        ans = ((j+1 == (int)vec.size()) ? -1 : (vec[j+1].first - 1));
        if(goal == tmp.by) ansV = k;
        else if(goal == tmp.ay) ansV = tmp.ax;
        else ansV = tmp.bx - (tmp.by - goal);
        i=j;
    }
    if(ans == -1){
        printf("infinity");
    }
    else printf("%lld %lld", ans, ansV);
}

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d %lld %lld", &n, &k, &goal);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf(" %c %lld", &c, &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 72 ms 700 KB Output is correct
3 Correct 2 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 16 ms 516 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 728 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3128 KB Output is correct
2 Correct 16 ms 3384 KB Output is correct
3 Correct 13 ms 3408 KB Output is correct
4 Correct 12 ms 3408 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3152 KB Output is correct
2 Correct 18 ms 3516 KB Output is correct
3 Correct 16 ms 3516 KB Output is correct
4 Correct 12 ms 3408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3252 KB Output is correct
2 Correct 21 ms 3600 KB Output is correct
3 Correct 26 ms 6260 KB Output is correct
4 Correct 14 ms 3520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5884 KB Output is correct
2 Correct 27 ms 6476 KB Output is correct
3 Correct 23 ms 6348 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 11456 KB Output is correct
2 Correct 59 ms 11456 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11592 KB Output is correct
2 Correct 59 ms 11568 KB Output is correct