oj.uz

Submission #866100

# Submission time Handle Problem Language Result Execution time Memory
866100 2023-10-25T12:13:11 Z byunjaewoo MP3 Player (CEOI10_mp3player) C++17
100 / 100
 42 ms 13260 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010, S=(1<<17);
int N, M, K, ans1, ans2;
int A[Nmax], B[Nmax];
vector<pair<int, int>> V;

class Seg {
public:
    struct Data {int l, r, lo, hi;}Tree[2*S];
    void Reset() { for(int i=1; i<2*S; i++) Tree[i]={0, M, 0, M}; }
    Data Merge(Data a, Data b) {
        Data ret;
        if(b.lo<=a.l) ret.lo=a.lo;
        else if(b.lo<=a.r) ret.lo=a.lo+(b.lo-a.l);
        else ret.lo=a.hi;
        if(b.hi<=a.l) ret.hi=a.lo;
        else if(b.hi<=a.r) ret.hi=a.lo+(b.hi-a.l);
        else ret.hi=a.hi;
        if(b.lo<=a.l) ret.l=b.l+(a.l-b.lo);
        else if(b.lo<=a.r) ret.l=b.l;
        else ret.l=1;
        ret.r=ret.l+(ret.hi-ret.lo);
        return ret;
    }
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            if(v==1) Tree[node]={0, M-1, 1, M};
            else Tree[node]={1, M, 0, M-1};
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Tree[node]=Merge(Tree[rch], Tree[lch]);
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>K;
    for(int i=1; i<=N; i++) {
        char op; cin>>op;
        if(op=='+') A[i]=1;
        else A[i]=-1;
        cin>>B[i];
    }
    for(int i=2; i<=N; i++) V.push_back({B[i]-B[i-1], i});
    sort(V.begin(), V.end());
    T.Reset();
    ans1=V[0].first-1, ans2=K;
    for(int i=0; i<V.size(); i++) {
        int p=i;
        for(int j=i; j<V.size() && V[i].first==V[j].first; j++) {
            T.Update(V[j].second, A[V[j].second]), p=j;
        }
        i=p;
        if(T.Tree[1].lo<=K && K<=T.Tree[1].hi) {
            if(i==V.size()-1) {
                cout<<"infinity"; return 0;
            }
            ans1=V[i+1].first-1;
            if(K==T.Tree[1].hi) ans2=M;
            else ans2=T.Tree[1].l+(K-T.Tree[1].lo);
        }
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:55:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0; i<V.size(); i++) {
      |                  ~^~~~~~~~~
mp3player.cpp:57:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=i; j<V.size() && V[i].first==V[j].first; j++) {
      |                      ~^~~~~~~~~
mp3player.cpp:62:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if(i==V.size()-1) {
      |                ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8916 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9432 KB Output is correct
2 Correct 8 ms 9432 KB Output is correct
3 Correct 8 ms 9692 KB Output is correct
4 Correct 7 ms 9576 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9436 KB Output is correct
2 Correct 9 ms 9436 KB Output is correct
3 Correct 9 ms 9436 KB Output is correct
4 Correct 7 ms 9436 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9688 KB Output is correct
2 Correct 13 ms 9688 KB Output is correct
3 Correct 13 ms 9688 KB Output is correct
4 Correct 8 ms 9824 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10200 KB Output is correct
2 Correct 15 ms 10196 KB Output is correct
3 Correct 12 ms 10456 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11728 KB Output is correct
2 Correct 35 ms 13260 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11732 KB Output is correct
2 Correct 32 ms 13012 KB Output is correct