Submission #1215388

#TimeUsernameProblemLanguageResultExecution timeMemory
1215388brintonRectangles (IOI19_rect)C++20
0 / 100
3 ms328 KiB
#include<bits/stdc++.h> #include "rect.h" using namespace std; long long count_rectangles(vector<vector<int> > a) { int N = a[0].size(); vector<int> bad(N,0); for(int i = 1;i < N-1;i++){ if(a[1][i] < a[0][i] && a[1][i] < a[2][i]){ bad[i] = false; }else{ bad[i] = true; } } for(int i = 1;i < N;i++){ bad[i] += bad[i-1]; } // sparse table; // int k = __lg(N)+1; // vector<vector<int>> spt(k,vector<int>(N)); // spt[0] = a[1]; // for(int layer = 1;layer < k;layer++){ // for(int s = 0;s+(1 << layer)-1 < N;s++){ // spt[layer][s] = max(spt[layer-1][s],spt[layer-1][s+(1 << (layer-1))]); // } // } // auto ask = [&](int l,int r){ // int len = r-l+1; // int layer = __lg(len); // return max(spt[layer][l],spt[layer][r-(1 << layer)+1]); // }; long long ans = 0; for(int l = 0;l < N;l++){ int cmax = a[1][l+1]; for(int r = l+2;r < N;r++){ // int midmax = ask(l+1,r-1); int midmax = cmax; // cout << "(" << l << "," << r << "):" << midmax << "," << bad[r-1]-bad[l] << endl; if(midmax < a[1][l] && midmax < a[1][r] && bad[r-1]-bad[l] == 0){ ans++; } cmax = max(cmax,a[1][r]); } } return ans; }
#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...