Submission #866096

#	Time	Username	Problem	Language	Result	Execution time	Memory
866096		byunjaewoo	MP3 Player (CEOI10_mp3player)	C++17	10 / 100	42 ms	11776 KiB

mp3player

#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=1; i<=N; i++) V.push_back({B[i]-B[i-1], i});
    sort(V.begin(), V.end());
    T.Reset();
    ans1=max(0ll, 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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10