(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #222368

#제출 시각아이디문제언어결과실행 시간메모리
222368lycGrudanje (COCI19_grudanje)C++14
70 / 70
916 ms11640 KiB
#include <bits/stdc++.h> using namespace std; #define SZ(x) (int)(x).size() #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define RFOR(i,a,b) for (int i=(a);i>=(b);--i) const int MX_N = 1e5+5; const int MX_Q = 1e5+5; string S; int N, Q, A[MX_Q], B[MX_Q], P[MX_N]; int nxt[MX_N], pos[26]; struct node { int s, e, m, v; node *l, *r; node(int s, int e): s(s), e(e), m((s+e)/2), v(0) { if (s != e) { l = new node(s,m); r = new node(m+1,e); } } void update(int i, int x) { if (s == e) { v = x; return; } if (i <= m) l->update(i,x); else r->update(i,x); v = min(l->v,r->v); } int query(int x, int y) { if (s == x && e == y) return v; else if (y <= m) return l->query(x,y); else if (x > m) return r->query(x,y); else return min(l->query(x,m),r->query(m+1,y)); } } *root; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> S; N = S.length(); cin >> Q; FOR(i,1,Q){ cin >> A[i] >> B[i]; --A[i], --B[i]; } FOR(i,1,N){ cin >> P[i]; --P[i]; } root = new node(0,N-1); int lo = -1, hi = N; while (hi-lo > 1) { int mid = (lo+hi)/2; string T(S); FOR(i,0,mid) T[P[i]] = '#'; FOR(i,0,25) pos[i] = N; RFOR(i,N-1,0){ if (T[i] == '#') nxt[i] = N; else { nxt[i] = pos[T[i]-'a']; pos[T[i]-'a'] = i; } root->update(i,nxt[i]); } bool ok = 1; FOR(i,1,Q){ ok &= root->query(A[i],B[i]) > B[i]; } //FOR(i,0,N-1) cout << nxt[i] << ' '; //cout << endl; //cout << "pos i " << mid << " :: " << ok << endl; if (ok) hi = mid; else lo = mid; } cout << lo+1 << '\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...