제출 #757049

#제출 시각아이디문제언어결과실행 시간메모리
757049doowey서열 (APIO23_sequence)C++17
28 / 100
2097 ms45764 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair const int N = (int)5e5 + 10; vector<int> pos[N]; int A[N]; int n; struct Node{ int low; int high; int lazy; }; Node T[N * 4 + 512]; void build(int node, int cl, int cr){ T[node].low = T[node].high = T[node].lazy = 0; if(cl == cr){ T[node].low = T[node].high = cl; T[node].lazy = 0; return; } int mid = (cl + cr) / 2; build(node * 2, cl, mid); build(node * 2 + 1, mid + 1, cr); T[node].low=min(T[node*2].low, T[node*2+1].low); T[node].high=max(T[node*2].high,T[node*2+1].high); } void push(int node, int cl, int cr){ T[node].high += T[node].lazy; T[node].low += T[node].lazy; if(cl != cr){ T[node * 2].lazy += T[node].lazy; T[node * 2 + 1].lazy += T[node].lazy; } T[node].lazy = 0; } void update_segm(int node, int cl, int cr, int tl, int tr, int d){ push(node, cl, cr); if(cr < tl || cl > tr) return; if(cl >= tl && cr <= tr){ T[node].lazy = d; push(node, cl, cr); return; } int mid = (cl + cr) / 2; update_segm(node * 2, cl, mid, tl, tr, d); update_segm(node * 2 + 1, mid + 1, cr, tl, tr, d); T[node].low=min(T[node*2].low, T[node*2+1].low); T[node].high=max(T[node*2].high,T[node*2+1].high); } pii get_val(int node, int cl, int cr, int tl, int tr){ push(node, cl, cr); if(cr < tl || cl > tr) return mp((int)1e9, -(int)1e9); if(cl >= tl && cr <= tr){ return mp(T[node].low, T[node].high); } int mid = (cl + cr) / 2; pii L = get_val(node * 2, cl, mid, tl, tr); pii R = get_val(node * 2 + 1, mid + 1, cr, tl, tr); return mp(min(L.fi, R.fi), max(L.se, R.se)); } mt19937 gene(chrono::steady_clock::now().time_since_epoch().count()); int numo(int m){ return ((int)gene() % m + m) % m; } bool check(int cnt){ build(1, 0, n); int bal; int l, r; pii suf; pii lE; pii rE; pii lef; int take; for(int cand = 1; cand <= n; cand ++ ){ for(auto x : pos[cand]){ update_segm(1, 0, n, x, n, -1); } for(int j = 0 ; j + cnt - 1 < pos[cand].size(); j ++ ){ l = pos[cand][j]; r = pos[cand][j + cnt - 1]; lE = get_val(1, 0, n, l - 1, l - 1); rE = get_val(1, 0, n, r, r); bal = rE.fi - lE.fi; suf = get_val(1, 0, n, r, n); lef = get_val(1, 0, n, 0, l - 1); suf.fi -= rE.fi; suf.se -= rE.se; lef = mp(-lef.se, -lef.fi); lef.fi += lE.fi; lef.se += lE.fi; bal += lef.fi + suf.fi; take = max(0, (-cnt) - bal); if(bal <= cnt && take <= (lef.se - lef.fi) + (suf.se - suf.fi)){ return true; } } for(auto x : pos[cand]){ update_segm(1, 0, n, x, n, -1); } } return false; } int sequence(int _n, vector<int> a) { n = _n; for(int i = 0 ; i < n; i ++ ){ A[i + 1] = a[i]; pos[A[i + 1]].push_back(i + 1); } int l = 1, r = n + 1; int mid; while(l + 1 < r){ mid = l + (r - l) / 2; if(check(mid)){ l = mid; } else{ r = mid; } } for(int iter = l + 12; iter >= l ; iter -- ){ if(iter <= n && check(iter)) return iter; } return l; }

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

sequence.cpp: In function 'bool check(int)':
sequence.cpp:97:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j = 0 ; j + cnt - 1 < pos[cand].size(); j ++ ){
      |                         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
#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...