Submission #1255976

#TimeUsernameProblemLanguageResultExecution timeMemory
1255976nerrrminRectangles (IOI19_rect)C++20
0 / 100
4 ms328 KiB
#include "rect.h" #define pb push_back using namespace std; const int maxn = 3e3 + 10; int n, m; int is[maxn], pref[maxn]; int arr[maxn]; //int t[maxn * 4]; /*void build(int i, int l, int r) { if(l == r) { t[i] = arr[l]; return; } int mid = (l + r)/2; build(2*i, l, mid); build(2*i+1, mid+1, r); t[i] = max(t[2*i], t[2*i+1]); } int ql, qr; int query(int i, int l, int r) { if(qr < l || ql > r)return 0; if(ql <= l && r <= qr)return t[i]; int mid = (l + r)/2; return max(query(2*i, l, mid), query(2*i+1, mid+1, r)); }*/ long long count_rectangles(std::vector<std::vector<int> > a) { n = a.size(); m = a[0].size(); for (int i = 0; i < m; ++ i) { arr[i] = a[1][i]; } if(n < 3)return 0; // build(1, 1, m-2); for (int i = 0; i < m; ++ i) { if(a[1][i] < a[0][i] && a[1][i] < a[2][i])is[i] = 1; } for (int i = 1; i < m; ++ i) pref[i] = pref[i-1] + is[i]; int ans = 0; for (int lt = 1; lt < m-1; ++ lt) { int mx = 0; for (int rt = lt; rt < m-1; ++ rt) { mx = max(mx, arr[rt]); int onl = lt - 1; int onr = rt + 1; int cntis = pref[rt] - pref[lt-1]; if(cntis == rt - lt + 1 && mx < min(a[1][onl], a[1][onr])) ans ++; } } 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...