제출 #568781

#제출 시각아이디문제언어결과실행 시간메모리
568781blueMP3 Player (CEOI10_mp3player)C++17
0 / 100
71 ms5100 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #define sz(x) int(x.size()) int N, Vmax, V2; vi A, C; vi D; const int INF = 2'000'000'005; struct func { int y1; int x1; int x2; int eval(int x) { if(x <= x1) return y1; else return y1 + min(x,x2) - x1; } }; func combine(func A, func B) { if(max(A.y1, B.x1) <= min(A.y1 + A.x2 - A.x1, B.x2)) return {B.eval(A.eval(0)), max(A.y1, B.x1) - A.y1 + A.x1, min(A.y1 + A.x2 - A.x1, B.x2) - A.y1 + A.x1}; else return {B.eval(A.eval(0)), 0, 0}; } func nothing; func plusone; func minusone; const int lg = 17; const int Z = (1<<lg); vector<func> segtree; void set(int i, func v) { segtree[Z+i] = v; for(int j = (Z+i)>>1; j >= 1; j >>= 1) segtree[j] = combine(segtree[2*j], segtree[2*j+1]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> Vmax >> V2; nothing = {0, 0, Vmax}; plusone = {1, 0, Vmax-1}; minusone = {0, 1, Vmax}; A = C = vi(1+N); for(int i = 1; i <= N; i++) { char c; cin >> c; A[i] = (c == '+' ? +1 : -1); cin >> C[i]; } D = vi(1+N); D[1] = INF; for(int i = 2; i <= N; i++) D[i] = C[i] - C[i-1]; vi I; for(int i = 1; i <= N; i++) I.push_back(i); int T = 0, V1 = V2; sort(I.begin(), I.end(), [] (int p, int q) { return D[p] < D[q]; }); int u = 0, v = 0; segtree = vector<func>((1<<(lg+1)) + 1, nothing); for(u = 0; u < N-1; u++) { int currlim = D[I[u]]; for(v = u; v < N-1 && D[v] == D[u]; v++) { int i = I[v]; if(A[i] == +1) set(i, plusone); else set(i, minusone); // cerr << "activating : " << i << '\n'; } u = v-1; // cerr << "checking : " << currlim << '\n'; int y1 = segtree[1].y1, x1 = segtree[1].x1, x2 = segtree[1].x2; int y2 = y1+x2-x1; if(y1 <= V2 && V2 <= y2) { int currV1 = (y2 == V2 ? Vmax : y2-y1+x1); if(currlim > T || (currlim == T && currV1 > V1)) { T = currlim; V1 = currV1; } } } if(T == INF) cout << "infinity\n"; else cout << T << ' ' << V1 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...