# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
441653 | 2021-07-05T17:17:33 Z | linkret | Global Warming (CEOI18_glo) | C++14 | 337 ms | 31680 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], dp1[i]); sol=max (sol, res); } cout << sol << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 337 ms | 31680 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 77 ms | 15940 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 153 ms | 27688 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |