Submission #1047622

#TimeUsernameProblemLanguageResultExecution timeMemory
1047622vjudge1Rectangles (IOI19_rect)C++17
0 / 100
3 ms604 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int lim=3000; struct{ int tree[lim]; void clear(){ fill(tree,tree+lim,0); } void update(int p,int val){ p++; while(p<lim){ tree[p]+=val; p+=p&-p; } } int query(int p){ p++; int ans=0; while(p){ ans+=tree[p]; p-=p&-p; } return ans; } int query(int l,int r){ if(r<l)return 0; return query(r)-query(l-1); } }fw; long long count_rectangles(std::vector<std::vector<int> > a) { int n=a.size(); int m=a[0].size(); if(n==3){ int l[m]; stack<int>st; for(int i=0;i<m;i++){ while(st.size()&&a[1][st.top()]<a[1][i]){ st.pop(); } if(st.size()){ l[i]=st.top(); }else{ l[i]=0; } st.push(i); } int r[m]; while(st.size())st.pop(); for(int i=m-1;0<=i;i--){ while(st.size()&&a[1][st.top()]<a[1][i]){ st.pop(); } if(st.size()){ r[i]=st.top(); }else{ r[i]=m; } st.push(i); } vector<int>torem[m+5]; long int ans=0; for(int i=0;i<m;i++){ for(int j:torem[i]){ //cerr<<"removed "<<j<<" at "<<i<<"\n"; fw.update(j,-1); } if(1<i&&l[i]<=i-2){ int k=fw.query(l[i],i-2); //cerr<<"queried "<<l[i]<<" "<<i-2<<"\n"; //cerr<<k<<"\n"; ans+=k; } if(a[1][i]>=a[0][i]||a[1][i]>=a[2][i]){ //cerr<<"clear at "<<i<<"\n"; fw.clear(); for(int j=i;j<m;j++){ torem[j].clear(); } } fw.update(i,1); torem[r[i]+1].push_back(i); } return ans; } return -1; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...