제출 #870747

#제출 시각아이디문제언어결과실행 시간메모리
870747salmon서열 (APIO23_sequence)C++17
12 / 100
2009 ms90408 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; int N; int miin[500100 * 4]; int maax[500100 * 4]; int lazy[500100 * 4]; vector<int> in[500100]; vector<int> sat; void build(int i, int s, int e){ miin[i] = - e - 1; maax[i] = - s - 1; lazy[i] = 0; if(s != e){ int m = (s + e + 2)/2 - 1; build(i * 2, s, m); build(i * 2 + 1, m + 1, e); } } void update(int i, int s, int e, int S){ if(S <= s){ miin[i] += 2; maax[i] += 2; lazy[i] += 2; return; } int m = (s + e + 2)/2 - 1; update(i * 2 + 1, m + 1, e, S); if(S <= m){ update(i * 2, s, m, S); } miin[i] = min(miin[i * 2], miin[i * 2 + 1]) + lazy[i]; maax[i] = max(maax[i * 2], maax[i * 2 + 1]) + lazy[i]; } pair<int,int> query(int i, int s, int e, int S, int E){ if(S <= s && e <= E){ return make_pair(miin[i],maax[i]); } int m = (s + e + 2)/2 - 1; pair<int,int> ii,ii1; if(S <= m && m < E){ ii = query(i * 2, s, m, S, E); ii1 = query(i * 2 + 1, m + 1, e, S, E); ii.first = min(ii.first, ii1.first) + lazy[i]; ii.second = max(ii.second, ii1.second) + lazy[i]; } else if(S <= m){ ii = query(i * 2, s, m, S, E); ii.first = ii.first + lazy[i]; ii.second = ii.second + lazy[i]; } else{ ii = query(i * 2 + 1, m + 1, e, S, E); ii.first = ii.first + lazy[i]; ii.second = ii.second + lazy[i]; } return ii; } int sequence(int N, std::vector<int> lst) { for(int i = 0; i < N; i++){ in[lst[i]].push_back(i); } int s,e,m; s = 1; e = N; while(s != e){ m = (s + e + 1)/2; build(1,-1,N-1); bool flag = false; for(int i = 1; i <= N; i++){ sat.clear(); //printf("mah %d %d \n",m,i); sat.push_back(-1); vector<int> v; v.push_back(0); for(int j = 0; j < in[i].size() ; j++){ sat.push_back(in[i][j]); } sat.push_back(N); for(int j = 1; j <= ((int)in[i].size()) - m + 1; j++){ pair<int,int> ii = query(1,-1,N - 1,-1,sat[j + 1] - 1); pair<int,int> ii1 = query(1, -1, N - 1, sat[j + m], N - 1); v.push_back(ii1.first - ii.second); } for(int j = 0; j < in[i].size() ; j++){ update(1,-1,N-1,in[i][j]); } for(int j = 1; j <= ((int)in[i].size()) - m + 1; j++){ pair<int,int> ii = query(1,-1,N - 1,-1,sat[j] - 1); pair<int,int> ii1 = query(1, -1, N - 1, sat[j + m - 1], N - 1); //printf("\n%d %d\n",ii.first,ii.second); //printf("%d %d\n",ii1.first,ii1.second); if( (ii1.second - ii.first) * v[i] > 0) continue; else{ flag = true; break; } } if(flag) break; } if(flag){ s = m; } else{ e = m - 1; } } return s; }

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

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