제출 #757460

#제출 시각아이디문제언어결과실행 시간메모리
757460yellowtoad서열 (APIO23_sequence)C++17
40 / 100
2077 ms56952 KiB
#include "sequence.h" #include <iostream> #include <vector> using namespace std; int n, a[500010], maxx, node[2000010][2][2], lz[2000010][2][2]; // 0: updated, 1: not updated; 0: max, 1: min vector<int> pos[500010]; inline void build(int id, int x, int y) { if (x == y) { node[id][0][0] = node[id][0][1] = node[id][1][1] = node[id][1][0] = x; return; } int mid = (x+y)/2; build(id*2,x,mid); build(id*2+1,mid+1,y); node[id][0][0] = max(node[id*2][0][0],node[id*2+1][0][0]); node[id][1][0] = max(node[id*2][1][0],node[id*2+1][1][0]); node[id][0][1] = min(node[id*2][0][1],node[id*2+1][0][1]); node[id][1][1] = min(node[id*2][1][1],node[id*2+1][1][1]); } inline void update(int i, int j, int id, int x, int y, int l, int r) { if ((l <= x) && (y <= r)) { node[id][i][j] -= 2; lz[id][i][j] -= 2; return; } if ((y < l) || (r < x)) return; int mid = (x+y)/2; node[id*2][i][j] += lz[id][i][j]; node[id*2+1][i][j] += lz[id][i][j]; lz[id*2][i][j] += lz[id][i][j]; lz[id*2+1][i][j] += lz[id][i][j]; lz[id][i][j] = 0; update(i,j,id*2,x,mid,l,r); update(i,j,id*2+1,mid+1,y,l,r); if (!j) node[id][i][j] = max(node[id*2][i][j],node[id*2+1][i][j]); else node[id][i][j] = min(node[id*2][i][j],node[id*2+1][i][j]); } inline int query(int i, int j, int id, int x, int y, int l, int r) { if ((l <= x) && (y <= r)) return node[id][i][j]; if ((y < l) || (r < x)) { if (!j) return -1e9; else return 1e9; } int mid = (x+y)/2; node[id*2][i][j] += lz[id][i][j]; node[id*2+1][i][j] += lz[id][i][j]; lz[id*2][i][j] += lz[id][i][j]; lz[id*2+1][i][j] += lz[id][i][j]; lz[id][i][j] = 0; if (!j) return max(query(i,j,id*2,x,mid,l,r),query(i,j,id*2+1,mid+1,y,l,r)); else return min(query(i,j,id*2,x,mid,l,r),query(i,j,id*2+1,mid+1,y,l,r)); } int sequence(int N, std::vector<int> A) { n = N; for (int i = 1; i <= n; i++) { a[i] = A[i-1]; pos[a[i]].push_back(i); } build(1,0,n); for (int i = 1; i <= n; i++) { for (int j = 0; j < pos[i].size(); j++) { update(0,0,1,0,n,pos[i][j],n); update(0,1,1,0,n,pos[i][j],n); } int l = 0, r = 0; while (r < pos[i].size()) { if ((query(1,0,1,0,n,pos[i][r],n)-query(1,1,1,0,n,0,pos[i][l]-1))*(query(0,1,1,0,n,pos[i][r],n)-query(0,0,1,0,n,0,pos[i][l]-1)) <= 0) r++; else l++; maxx = max(maxx,r-l); } for (int j = 0; j < pos[i].size(); j++) { update(1,0,1,0,n,pos[i][j],n); update(1,1,1,0,n,pos[i][j],n); } } return maxx; }

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

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j < pos[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (r < pos[i].size()) {
      |                ~~^~~~~~~~~~~~~~~
sequence.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 0; j < pos[i].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...