제출 #955113

#제출 시각아이디문제언어결과실행 시간메모리
955113Otalp서열 (APIO23_sequence)C++17
100 / 100
1719 ms672268 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define pb push_back #define ff first #define ss second int a[500100], b[500100]; int s1[500100], s2[500100], c[500100]; struct node{ pii x={1e9, -1e9}; node *l = nullptr, *r = nullptr; node(){} }; void upd(node *v, int l, int r, int pos, int x){ if(l == r){ v -> x = {min(v -> x.ff, x), max(v -> x.ss, x)}; return; } int mid = floor(((double)l + (double)r) / 2); if(mid >= pos){ if(!v -> l) v->l = new node(); upd(v -> l, l, mid, pos, x); } else{ if(!v -> r) v->r = new node(); upd(v->r, mid+1, r, pos, x); } v -> x = {1e9, -1e9}; if(v -> l) v -> x = {min(v -> x.ff, v -> l -> x.ff), max(v -> x.ss, v -> l -> x.ss)}; if(v -> r) v -> x = {min(v -> x.ff, v -> r -> x.ff), max(v -> x.ss, v -> r -> x.ss)}; } pii get(node *v, int l, int r, int L, int R){ if(r < L or R < l){ return {1e9, -1e9}; } if(L <= l and r <= R){ return v -> x; } int mid=floor(((double)l + (double)r) / 2); pii x = {1e9, -1e9}; if(v -> l){ pii k = get(v -> l, l, mid, L, R); x = {min(x.ff, k.ff), max(x.ss, k.ss)}; } if(v -> r){ pii k = get(v -> r, mid + 1, r, L, R); x = {min(x.ff, k.ff), max(x.ss, k.ss)}; } return x; } pii t[2000100]; int p[2001000]; void push(int v){ if(!p[v]) return; t[v+v].ff += p[v]; t[v+v+1].ff += p[v]; t[v+v].ss += p[v]; t[v+v+1].ss += p[v]; p[v+v] += p[v]; p[v+v+1] += p[v]; p[v] = 0; } void updq(int v, int l, int r, int L, int R, int x){ if(r < L or R < l){ return; } if(L <= l and r <= R){ t[v].ff += x; t[v].ss += x; p[v] += x; return; } int mid=(l+r)/2; push(v); updq(v+v, l, mid, L, R, x); updq(v+v+1, mid+1, r, L, R, x); t[v] = {min(t[v+v].ff, t[v+v+1].ff), max(t[v+v].ss, t[v+v+1].ss)}; } pii getq(int v, int l, int r, int L, int R){ if(r < L or R < l){ return {1e9, -1e9}; } if(L <= l and r <= R){ return t[v]; } int mid=(l+r)/2; push(v); pii k1=getq(v+v, l, mid, L, R), k2=getq(v+v+1, mid+1, r, L, R); return {min(k1.ff, k2.ff), max(k1.ss, k2.ss)}; } vector<int> pos[500100]; int sequence(int n, vector<int> A) { int ans = 0; for(int i=1; i<=n; i++){ a[i] = A[i - 1]; pos[a[i]].pb(i); } for(int i=1; i<=n; i++){ b[i] = 1; updq(1, 0, n, i, n, 1); } for(int x=1; x<=n; x++){ if(pos[x].size() == 0) continue; int ls = 0; vector<pii> q; for(int i=0; i<pos[x].size(); i++){ updq(1, 0, n, pos[x][i], n, -b[pos[x][i]]); b[pos[x][i]] = 0; q.pb(getq(1, 0, n, ls, pos[x][i])); ls = pos[x][i]; } q.pb(getq(1, 0, n, ls, n)); vector<pair<pii, int> > zap; for(int i=0; i<q.size(); i++){ zap.pb({{q[i].ss + i, q[i].ff-i}, i}); } vector<pair<pii, int> > h; for(int i=0; i<q.size(); i++){ h.pb({{q[i].ff+i, q[i].ss-i}, i}); } sort(h.begin(), h.end()); sort(zap.begin(), zap.end()); ls = 0; node *t = new node(); int d = n + 1; for(int i=0; i<zap.size(); i++){ int L=zap[i].ff.ff, R=zap[i].ff.ss; while(ls < h.size() and h[ls].ff.ff <= L){ upd(t, d - n, d + n, h[ls].ff.ss + d, h[ls].ss); ls++; } pii dd = get(t, d-n, d+n, d+R, d+n); ans = max(ans, max(zap[i].ss - dd.ff, dd.ss - zap[i].ss)); } for(int i: pos[x]){ updq(1, 0, n, i, n, -1); b[i] = -1; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int i=0; i<pos[x].size(); i++){
      |                      ~^~~~~~~~~~~~~~
sequence.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int i=0; i<q.size(); i++){
      |                      ~^~~~~~~~~
sequence.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int i=0; i<q.size(); i++){
      |                      ~^~~~~~~~~
sequence.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         for(int i=0; i<zap.size(); i++){
      |                      ~^~~~~~~~~~~
sequence.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |             while(ls < h.size() and h[ls].ff.ff <= L){
      |                   ~~~^~~~~~~~~~
#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...