# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
441654 | 2021-07-05T17:21:00 Z | linkret | Global Warming (CEOI18_glo) | C++14 | 323 ms | 29820 KB |
#include <bits/stdc++.h> using namespace std; int h [300000]; int fen [500002]; vector <int> pom; map <int, int> comp; int dp1 [300000]; int dp2 [300000]; const int MAXN = 500000+1; //fenwick int query (int x){ int sol=0; for (x; x>0; x-= (x & -x)) sol=max (sol, fen[x]); return sol; } void add (int x, int val){ for (x; x<500002; x+= (x & -x)) fen [x]=max (fen[x], val); } int main(){ //input int n, x; cin >> n >> x; for (int i=0; i<n; i++) cin >> h[i]; //compression for (int i=0; i<n; i++) pom.push_back(h[i]); for (int i=0; i<n; i++) pom.push_back(h[i]+x); sort (pom.begin(), pom.end()); for (int i=0; i<pom.size(); i++) comp [pom[i]]=i+1; //precompute right dynamic for (int i=n-1; i>=0; i--){ int hi=comp[h[i]]; int height=MAXN-hi; dp2 [i]=query (height)+1; add (height+1, dp2[i]); } //for (int i=0; i<n; i++) cout << dp2[i] << " "; memset (fen, 0, sizeof (fen)); //computing result int sol=0; for (int i=0; i<n; i++){ int hi=comp[h[i]+x]; int res=query (hi)+dp2[i]; dp1 [i]=query (h[i])+1; add (h[i]+1, dp1[i]); sol=max (sol, res); } cout << sol << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2252 KB | Output is correct |
2 | Correct | 1 ms | 2252 KB | Output is correct |
3 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2252 KB | Output is correct |
2 | Correct | 1 ms | 2252 KB | Output is correct |
3 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2252 KB | Output is correct |
2 | Correct | 1 ms | 2252 KB | Output is correct |
3 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 323 ms | 29820 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 75 ms | 15420 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 152 ms | 26512 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2252 KB | Output is correct |
2 | Correct | 1 ms | 2252 KB | Output is correct |
3 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |