제출 #532268

#제출 시각아이디문제언어결과실행 시간메모리
532268HaYoungJoonGlobal Warming (CEOI18_glo)C++14
0 / 100
262 ms8328 KiB
#include <bits/stdc++.h> #define INF 1e9 + 7 using namespace std; typedef pair<int,int> pii; int n, X, a[200001], b[200001], res1[200001], res2[200001], L[200001]; map<int,int> mp; int t[800001], posinIT[200001]; void update(int v, int tl, int tr, int pos, int val) { if (tl == tr) { t[v] = val; return; } int tm = (tl + tr)/2; if (pos <= tm) update(2*v,tl,tm,pos,val); else update(2*v+1,tm+1,tr,pos,val); t[v] = max(t[2*v],t[2*v+1]); } int getMax(int v, int tl, int tr, int l, int r) { if (l > r) return -INF; if (tl > r || tr < l) return -INF; if (tl >= l && tr <= r) return t[v]; int tm = (tl + tr)/2; return max(getMax(2*v,tl,tm,l,r),getMax(2*v+1,tm+1,tr,l,r)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> X; vector<pii> tmp; for (int i = 1; i <= n; i++) { cin >> a[i]; tmp.push_back(pii(a[i],i)); } sort(tmp.begin(),tmp.end()); int cnt = 1; for (int i = 0; i < tmp.size(); i++) posinIT[tmp[i].second] = i+1; int lis = 0; for (int i = n; i >= 1; i--) { int pos = upper_bound(L,L + lis, -a[i]) - L; L[pos] = -a[i]; res1[i] = pos + 1; update(1,1,n,posinIT[i],res1[i]); lis = max(lis, pos + 1); } for (int i = 1; i <= n; i++) a[i] -= X; lis = 0; for (int i = 1; i <= n; i++) { int pos = upper_bound(L,L + lis, a[i]) - L; L[pos] = a[i]; res2[i] = pos + 1; lis = max(lis, pos + 1); } int res = 0; for (int i = 1; i <= n; i++) { pii A = pii(a[i],INF); update(1,1,n,posinIT[i], -INF); int l = upper_bound(tmp.begin(),tmp.end(),A) - tmp.begin() + 1; int cur = max(0,getMax(1,1,n, l, n)); res = max(res,res2[i] + cur); } cout << res; return 0; }

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

glo.cpp: In function 'int main()':
glo.cpp:41: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]
   41 |     for (int i = 0; i < tmp.size(); i++) posinIT[tmp[i].second] = i+1;
      |                     ~~^~~~~~~~~~~~
glo.cpp:40:9: warning: unused variable 'cnt' [-Wunused-variable]
   40 |     int cnt = 1;
      |         ^~~
#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...