제출 #759316

#제출 시각아이디문제언어결과실행 시간메모리
759316Luicosas서열 (APIO23_sequence)C++17
100 / 100
957 ms61084 KiB
#pragma GCC optimize("Ofast") #include "sequence.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define sz(x) (int)(x.size()) #define itr(x) x.begin(), x.end() #define ref(x) (*(x)) #ifdef LOC #define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n"; #else #define debug(...) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> ostream& operator << (ostream& out, vector<T> v) { for(auto& i : v) { out << i << " "; } return out; } struct node { int lb, rb, mn, mx, lazy, lc, rc; }; ostream& operator << (ostream& out, node v) { cout << v.lb << " " << v.rb << " " << v.mn << " " << v.mx << " " << v.lazy << " " << v.lc << " " << v.rc << " "; return out; } struct segtree { vector<node> nodes; segtree(int l, int r) { nodes.reserve((r - l + 1) * 2); build(l, r); } void build(int l, int r) { int idx = sz(nodes); nodes.push_back({l, r, l, r, 0, -1, -1}); if(l == r) { return; } int mid = (l + r) / 2; nodes[idx].lc = sz(nodes); build(l, mid); nodes[idx].rc = sz(nodes); build(mid + 1, r); } void sadd(int l, int r, int v, int idx = 0) { int lb = nodes[idx].lb, rb = nodes[idx].rb; if(r < lb || l > rb) { return; } if(l <= lb && r >= rb) { nodes[idx].lazy += v; return; } int lc = nodes[idx].lc, rc = nodes[idx].rc; sadd(l, r, v, lc); sadd(l, r, v, rc); nodes[idx].mx = max(nodes[lc].mx + nodes[lc].lazy, nodes[rc].mx + nodes[rc].lazy); nodes[idx].mn = min(nodes[lc].mn + nodes[lc].lazy, nodes[rc].mn + nodes[rc].lazy); } int qrymx(int l, int r, int idx = 0) { int lb = nodes[idx].lb, rb = nodes[idx].rb; if(r < lb || l > rb) { return INT_MIN; } if(l <= lb && r >= rb) { return nodes[idx].mx + nodes[idx].lazy; } int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0; ret = max(qrymx(l, r, lc), qrymx(l, r, rc)); return ret + nodes[idx].lazy; } int qrymn(int l, int r, int idx = 0) { int lb = nodes[idx].lb, rb = nodes[idx].rb; if(r < lb || l > rb) { return INT_MAX; } if(l <= lb && r >= rb) { return nodes[idx].mn + nodes[idx].lazy; } int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0; ret = min(qrymn(l, r, lc), qrymn(l, r, rc)); return ret + nodes[idx].lazy; } }; int sequence(int N, std::vector<int> A) { debug(N); debug(A); vector<int> sids(N); for(int i = 0; i < N; i++) { sids[i] = i; } sort(sids.begin(), sids.end(), [&](int a, int b) { if(A[a] != A[b]) { return A[a] < A[b]; } else { return a < b; } }); int ptr = 0, mx = 1; segtree eqpos(0, N), eqneg(0, N); while(ptr < N) { for(int i = ptr; i < N && A[sids[i]] == A[sids[ptr]]; i++) { eqneg.sadd(sids[i] + 1, N, -2); } int nptr = ptr; while(nptr < N && A[sids[nptr]] == A[sids[ptr]]) { if(nptr + mx >= N) { return mx; } int l = sids[nptr], r = sids[nptr + mx]; if(A[l] != A[r]) { nptr++; continue; } if(eqpos.qrymx(r + 1, N) - eqpos.qrymn(0, l) >= 0 && eqneg.qrymn(r + 1, N) - eqneg.qrymx(0, l) <= 0) { mx++; } else { nptr++; } } for(; ptr < nptr; ptr++) { eqpos.sadd(sids[ptr] + 1, N, -2); } } return mx; }
#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...