Submission #349282

#	Time	Username	Problem	Language	Result	Execution time	Memory
349282		ijxjdjd	MP3 Player (CEOI10_mp3player)	C++17	100 / 100	973 ms	13776 KiB

mp3player

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(1e5+5) + 5;
int mx[4*MAXN];
int mn[4*MAXN];
int lzy[4*MAXN];

int INF = (int)(1e8);
void push(int n) {
    lzy[2*n] += lzy[n];
    lzy[2*n+1] += lzy[n];
    mx[2*n] += lzy[n];
    mx[2*n+1] += lzy[n];
    mn[2*n] += lzy[n];
    mn[2*n+1] += lzy[n];
    lzy[n] = 0;
}
void pull(int n) {
    mx[n] = max(mx[2*n], mx[2*n+1]);
    mn[n] = min(mn[2*n], mn[2*n+1]);
}
void add(int l, int r, int v, int n = 1, int tl = 0, int tr = MAXN-1) {
    if (l > tr || r < tl) {
        return;
    }
    if (l <= tl && tr <= r) {
        mx[n] += v;
        mn[n] += v;
        lzy[n] += v;
        return;
    }
    push(n);
    int tm = (tl + tr)/2;
    add(l, r, v, 2*n, tl, tm);
    add(l, r, v, 2*n+1, tm+1, tr);
    pull(n);
}
void rem(int i, int n = 1, int tl = 0, int tr = MAXN-1) {
    if (tl == tr) {
        mx[n] = -INF;
        mn[n] = INF;
        return;
    }
    push(n);
    int tm = (tl + tr)/2;
    if (i <= tm) {
        rem(i, 2*n, tl, tm);
    }
    else {
        rem(i, 2*n+1, tm+1, tr);
    }
    pull(n);
}
int query(int l, int r, bool gmax, int n = 1, int tl = 0, int tr = MAXN-1) {
    if (l > tr || r < tl) {
        if (gmax) {
            return INT_MIN;
        }
        else {
            return INT_MAX;
        }
    }
    if (l <= tl && tr <= r) {
        if (gmax) {
            return mx[n];
        }
        else {
            return mn[n];
        }
    }
    push(n);
    int tm = (tl + tr)/2;
    int q1 = query(l, r, gmax, 2*n, tl, tm);
    int q2 = query(l, r, gmax, 2*n+1, tm+1, tr);
    if (gmax) {
        return max(q1, q2);
    }
    else {
        return min(q1, q2);
    }
}
void printPref(int N) {
    FR(i, N) {
        cout << query(i, i, true) << " ";
    }
    cout << endl;
}
int findNext(int l, bool gmax, int v, int N) {
    int ini = query(l, N-1, gmax);
    if (gmax) {
        if (ini >= v) {
            int r = N-1;
            while (l < r) {
                int mid = (l + r)/2;
                if (query(l, mid, gmax) >= v) {
                    r = mid;
                }
                else {
                    l = mid+1;
                }
            }
            return r;
        }
        return N;
    }
    else {
        if (ini <= v) {
            int r = N-1;
            while (l < r) {
                int mid = (l + r)/2;
                if (query(l, mid, gmax) <= v) {
                    r = mid;
                }
                else {
                    l = mid+1;
                }
            }
            return r;
        }
        return N;
    }
}

set<int> has;
struct Keep {
    int lzy[4*MAXN];
    Keep() {
        memset(lzy, 0, sizeof(lzy));
    }
    void add(int l, int r, int v, int n = 1, int tl = 0, int tr = MAXN-1) {
        if (l > tr || r < tl) {
            return;
        }
        if (l <= tl && tr <= r) {
            lzy[n] += v;
            return;
        }
        int tm = (tl + tr)/2;
        add(l, r, v, 2*n, tl, tm);
        add(l, r, v, 2*n+1, tm+1, tr);
    }
    int get(int i, int n = 1, int tl = 0, int tr = MAXN-1, int run = 0) {
        run += lzy[n];
        if (tl == tr) {
            return run;
        }
        int tm = (tl + tr)/2;
        if (i <= tm) {
            return get(i, 2*n, tl, tm, run);
        }
        return get(i, 2*n+1, tm+1, tr, run);
    }
    void upd(int n, int ad, int N, int Vmax) {
        int now = get(n);
        int curPref = query(n, n, true);
        int nt1;
        int nt2;
        if ((now == 0 || now == Vmax) && ((has.find(n) == has.begin()) || (get(*(prev(has.find(n)))) == now))) {
            return;
        }
        if (ad == -1) {
            nt1 = findNext(n+1, true, Vmax-now+curPref, N);
            nt2 = findNext(n+1, false, curPref-now-1, N);
        }
        else {
            nt1 = findNext(n+1, true, Vmax-now+curPref+1, N);
            nt2 = findNext(n+1, false, curPref-now, N);
        }

        if (nt1 > nt2) {
            swap(nt1, nt2);
        }
        add(n, nt1-1, -ad);
    }
    void print(int N) {
        FR(i, N) {
            cout << get(i) << " ";
        }
        cout << endl;
    }
};

int main() {
//    freopen("input.in", "r", stdin);
//    freopen("input.out", "w", stdout);
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, Vmax, V2;
//	N = 100;
//	Vmax = 100;
////	V2 = 35;
	cin >> N >> Vmax >> V2;
	N--;
	vector<pair<int, int>> added;
	char trash1;
	int last = 0;
	cin >> trash1 >> last;
	int arr[N];
//	cout << N << " " << Vmax << " " << V2 << endl;
	FR(i, N) {
	    char c;
	    cin >> c;
        arr[i] = (c == '+' ? 1 : -1);
//        arr[i] = (rand()%2 == 0 ? 1 : -1);
        add(i, N-1, arr[i]);
        int cur;
        cin >> cur;
//        cur = last + rand()%25 + 1;
//        cout << arr[i] << " " << cur << endl;
        added.push_back({cur-last, i});
        last = cur;
	}
	sort(added.begin(), added.end());
	Keep v0, vm;
	int inimax = Vmax;
	int inimin = 0;
	FR(i, N) {
        inimax += arr[i];
        inimin += arr[i];
        inimax = max(0, min(inimax, Vmax));
        inimin = max(0, min(inimin, Vmax));
        vm.add(i, i, inimax);
        v0.add(i, i, inimin);
        has.insert(i);
	}
//    v0.print(N);
//	vm.print(N);
//	printPref(N);
	last = -1;
	while (added.size()) {
        int store = 0;
//        FR(i, N) {
//            store += arr[i];
//            store = max(0, min(Vmax, store));
//            if (arr[i] != 0 && store != v0.get(i)) {
//                cout << "Diff: " << endl;
//                v0.print(N);
//                cout << i << " " << store << endl;
//            }
//        }
        if (v0.get(*has.rbegin()) <= V2 && V2 <= vm.get(*has.rbegin())) {
            break;
        }
        int cur = added.back().first;
        while (added.size() && added.back().first == cur) {
            vm.upd(added.back().second, arr[added.back().second], N, Vmax);
//            vm.print(N);
            v0.upd(added.back().second, arr[added.back().second], N, Vmax);
//            v0.print(N);
//            cout << added.back().second << " " << arr[added.back().second] << endl;
            add(added.back().second, N-1, -arr[added.back().second]);
            rem(added.back().second);
            arr[added.back().second] = 0;
            has.erase(has.find(added.back().second));
//            printPref(N);
            added.pop_back();
        }
        last = cur;
	}
	if (last == -1) {
        cout << "infinity";
	}
	else  {
        int low = 0;
        int high = Vmax;
        while (low < high) {
            int mid = (low + high+1)/2;
            int cur = mid;
            FR(i, N) {
                cur += arr[i];
                cur = max(0, min(Vmax, cur));
            }
            if (cur <= V2) {
                low = mid;
            }
            else {
                high = mid-1;
            }
        }
        int cur = low;
        FR(i, N) {
            cur += arr[i];
            cur = max(0, min(Vmax, cur));
        }
        cout << last-1 << " " << low;
	}
	return 0;
}

Compilation message (stderr)

mp3player.cpp: In function 'int main()':
mp3player.cpp:235:13: warning: unused variable 'store' [-Wunused-variable]
  235 |         int store = 0;
      |             ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10