| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1215386 | brinton | Split the Attractions (IOI19_split) | C++20 | 0 ms | 0 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[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;
}