# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
70987 |
2018-08-24T01:02:50 Z |
노영훈(#2202) |
Global Warming (CEOI18_glo) |
C++11 |
|
203 ms |
4204 KB |
#include <bits/stdc++.h>
using namespace std;
const int MX=200010, inf=2e9+1;
int n, A[MX], x, lim;
vector<int> X={-inf};
struct Seg{
int tree[1<<19];
void upt(int v, int s, int e, int x, int val){
if(x<s || e<x) return;
if(s==e){ tree[v]=val; return; }
upt(v*2,s,(s+e)/2,x,val);
upt(v*2+1,(s+e)/2+1,e,x,val);
tree[v]=max(tree[v*2],tree[v*2+1]);
}
void upt(int x, int v){
upt(1,0,lim,x,v);
}
int mx(int v, int s, int e, int r){
if(e<=r) return tree[v];
int m=(s+e)/2;
if(r<=m) return mx(v*2,s,m,r);
else return max(mx(v*2,s,m,r), mx(v*2+1,m+1,e,r));
}
int mx(int r){
return mx(1,0,lim,r);
}
} S1, S2;
int find(int x){
return upper_bound(X.begin(), X.end(), x)-X.begin()-1;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>x;
for(int i=1; i<=n; i++) cin>>A[i], X.push_back(A[i]);
sort(X.begin(), X.end());
lim=unique(X.begin(), X.end())-X.begin();
X.resize(lim); lim--;
for(int i=1; i<=n; i++){
int p1=find(A[i]);
S1.upt(p1, S1.mx(p1)+1);
}
cout<<S1.mx(lim)<<'\n';
/*
for(int i=1; i<=n; i++){
int p1=find(A[i]), p2=find(A[i]+x-1);
int a=mx(tree[0], p1), b=mx(tree[1], p1), c=mx(tree[0], p2);
upt(tree[0], p1, a+1);
upt(tree[1], p1, b+1);
upt(tree[1], p1, c+1);
}
cout<<mx(tree[1], lim)<<'\n';
*/
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
4204 KB |
Output is correct |
2 |
Correct |
192 ms |
4204 KB |
Output is correct |
3 |
Correct |
188 ms |
4204 KB |
Output is correct |
4 |
Correct |
191 ms |
4204 KB |
Output is correct |
5 |
Incorrect |
78 ms |
4204 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
4204 KB |
Output is correct |
2 |
Correct |
41 ms |
4204 KB |
Output is correct |
3 |
Correct |
40 ms |
4204 KB |
Output is correct |
4 |
Incorrect |
31 ms |
4204 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
95 ms |
4204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |