제출 #949977

#제출 시각아이디문제언어결과실행 시간메모리
949977berrCloud Computing (CEOI18_clo)C++17
0 / 100
1 ms3420 KiB
#include <bits/stdc++.h> using namespace std; int st[4*200000+37]; map<int, int> c, e; void update(int v, int l, int r, int pos, int val){ if (l==r){ st[v] = val; return;} int mid = (r+l) / 2; if (pos <= mid) update(v*2, l, mid, pos, val); else update(v*2+1, mid+1, r, pos, val); st[v] = max(st[v*2+1], st[v*2]); } int get(int v, int l, int r, int tl, int tr){ if(r<l || tl > r || tr < l || tr<tl) return 0; if(l>=tl && r<= tr) return st[v]; int mid = (r+l) / 2; return max(get(v*2, l, mid, tl, tr), get(v*2+1, mid+1, r, tl, tr)); } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, x; cin >> n >> x; vector<int> a(n); vector<int> b, d, rb, rd; for (auto &i: a) cin >> i; for (int i = 0; i < n; i++){ b.push_back(a[i]); d.push_back(a[i]-x); } sort(b.begin(), b.end()); sort(d.begin(), d.end()); int cnt=0; for (int i = 0; i < b.size(); i++){ if(c.count(b[i])==0) c[b[i]] = cnt, cnt++; } cnt=0; for(int i=0; i<n; i++){ if(e.count(d[i])==0) e[d[i]] = cnt, cnt++; } vector<int> pr(n), sf(n); int ans=0; for(int i=n-1; i>=0; i--){ sf[i] = max(0, get(1, 0, n+1, c[a[i]]+1, n+1)) +1; ans=max(ans, sf[i]); update(1, 0, n+1, c[a[i]], sf[i]); } memset(st, 0, sizeof(st)); for(int i=0; i<n; i++){ int s=-1; for(int l=20; l>=0; l--){ int tmp=s+(1LL<<l); if(tmp<n &&d[tmp] < a[i]){ s=tmp; } } if(s!=-1) ans=max(ans, max(0, get(1, 0, n+1, 0, e[d[s]]))+sf[i]); pr[i] = max(0, get(1, 0, n+1, 0, e[a[i]-x]-1)) +1; update(1, 0, n+1, e[a[i]-x], pr[i]); } cout<<ans; }

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

clo.cpp: In function 'int32_t main()':
clo.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < b.size(); i++){
      |                     ~~^~~~~~~~~~
#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...