# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
970214 | 2024-04-26T08:09:47 Z | amirhoseinfar1385 | The short shank; Redemption (BOI21_prison) | C++17 | 76 ms | 95068 KB |
#include<bits/stdc++.h> using namespace std; const int maxn=2000000+10; long long n,k,t,inf=1e9+5; int all[maxn],res=0; vector<pair<int,int>>allq; set<int>alld[maxn]; void vorod(){ cin>>n>>k>>t; for(int i=1;i<=n;i++){ cin>>all[i]; } } void calbaz(){ all[0]=inf; vector<int>v; v.push_back(0); for(int i=1;i<=n;i++){ while((int)v.size()>0&&all[v.back()]+(i-v.back())>=all[i]){ v.pop_back(); } while((int)v.size()>0&&all[v.back()]+(i-v.back())>=t){ v.pop_back(); } if(all[i]>t){ if((int)v.size()==0){ res++; }else{ allq.push_back(make_pair(v.back(),i-1)); } } v.push_back(i); } } void aval(){ for(int i=0;i<allq.size();i++){ for(int j=allq[i].first;j<=allq[i].second;j++){ alld[j].insert(i); } } } void pre(){ calbaz(); aval(); } int getmx(){ int wh=-1,mn=0; for(int i=1;i<=n;i++){ if((int)alld[i].size()>mn){ mn=(int)alld[i].size(); wh=i; } } return wh; } void remove(int ind){ if(ind==-1){ return ; } res+=(int)alld[ind].size(); set<int>hey=alld[ind]; for(auto x:hey){ for(int j=allq[x].first;j<=allq[x].second;j++){ alld[j].erase(x); } } } void cal(){ int ind=getmx(); remove(ind); } void solve(){ for(int i=0;i<k;i++){ cal(); } } void khor(){ res=n-res; cout<<res<<"\n"; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen("inp.txt","r",stdin); vorod(); pre(); solve(); khor(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 76 ms | 95060 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 95068 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 76 ms | 95060 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 95064 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 76 ms | 95060 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 76 ms | 95060 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |