Submission #1060802

#TimeUsernameProblemLanguageResultExecution timeMemory
1060802jamesbamberRectangles (IOI19_rect)C++17
72 / 100
5091 ms741096 KiB
#include "rect.h" #include <bits/stdc++.h> #pragma GCC target("avx2") using namespace std; struct segment{ vector<short> tr; int sz; segment(vector<int> &v){ sz = 1; while(sz <= v.size()) sz *= 2; tr.resize(2*sz); for(int i=0; i<v.size(); i++) tr[i+sz] = v[i]; for(int i=sz; --i;) tr[i] = max(tr[2*i], tr[2*i+1]); } segment() {} int query(int l, int r){ short ans = 0; for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){ if(l & 1) ans = max(ans, tr[l++]); if(r & 1) ans = max(ans, tr[--r]); } return ans; } }; struct segment2d{ vector<segment> tr; int sz; segment2d(vector<vector<int>> &v){ sz = 1; while(sz <= v.size()) sz *= 2; tr.resize(2*sz); int sz2 = v[0].size(); vector<int> ilvuoto(sz2); for(int i=0; i<v.size(); i++) tr[i+sz] = segment(v[i]); for(int i=v.size(); i<sz; i++) tr[i+sz] = segment(ilvuoto); for(int i=sz; --i;){ vector<int> treesus(sz2); for(int j=0; j<sz2; j++) treesus[j] = max(tr[2*i].tr[j+tr[2*i].sz], tr[2*i+1].tr[j+tr[2*i+1].sz]); tr[i] = segment(treesus); } } int query(int l, int r, int ql, int qr){ int ans = 0; for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){ if(l & 1) ans = max(ans, tr[l++].query(ql, qr)); if(r & 1) ans = max(ans, tr[--r].query(ql, qr)); } return ans; } }; struct segment2{ vector<short> tr; int sz; segment2(vector<int> &v){ sz = 1; while(sz <= v.size()) sz *= 2; tr.resize(2*sz); for(int i=0; i<v.size(); i++) tr[i+sz] = v[i]; for(int i=v.size(); i<sz; i++) tr[i+sz] = 1e4; for(int i=sz; --i;) tr[i] = min(tr[2*i], tr[2*i+1]); } segment2() {} int query(int l, int r){ short ans = 1e4; for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){ if(l & 1) ans = min(ans, tr[l++]); if(r & 1) ans = min(ans, tr[--r]); } return ans; } }; struct segment22d{ vector<segment2> tr; int sz; segment22d(vector<vector<int>> &v){ sz = 1; while(sz <= v.size()) sz *= 2; tr.resize(2*sz); int sz2 = v[0].size(); vector<int> ilgrosso(sz2, 1e9); for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]); for(int i=v.size(); i<sz; i++) tr[i+sz] = segment2(ilgrosso); for(int i=sz; --i;){ vector<int> treesus(sz2, 1e9); for(int j=0; j<sz2; j++) treesus[j] = min(tr[2*i].tr[j+tr[2*i].sz], tr[2*i+1].tr[j+tr[2*i+1].sz]); tr[i] = segment2(treesus); } } int query(int l, int r, int ql, int qr){ int ans = 1e9; for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){ if(l & 1) ans = min(ans, tr[l++].query(ql, qr)); if(r & 1) ans = min(ans, tr[--r].query(ql, qr)); } return ans; } }; long long count_rectangles(vector<vector<int>> a) { int n = a.size(); int m = a[0].size(); vector<vector<int>> up(n, vector<int>(m, -1)), down(n, vector<int>(m, n)), left(n, vector<int>(m, -1)), right(n, vector<int>(m, m)); //right for(int i=0; i<n; i++){ stack<int> s; for(int j=0; j<m; j++){ while(s.size() and a[i][s.top()] < a[i][j]){ right[i][s.top()] = j; s.pop(); } s.push(j); } } //left for(int i=0; i<n; i++){ stack<int> s; for(int j=m-1; j>=0; j--){ while(s.size() and a[i][s.top()] < a[i][j]){ left[i][s.top()] = j; s.pop(); } s.push(j); } } //up for(int j=0; j<m; j++){ stack<int> s; for(int i=n-1; i>=0; i--){ while(s.size() and a[s.top()][j] < a[i][j]){ up[s.top()][j] = i; s.pop(); } s.push(i); } } //down for(int j=0; j<m; j++){ stack<int> s; for(int i=0; i<n; i++){ while(s.size() and a[s.top()][j] < a[i][j]){ down[s.top()][j] = i; s.pop(); } s.push(i); } } int ans = 0; vector<array<int, 4>> grind; segment2d stright(right), stdown(down); segment22d stleft(left), stup(up); for(int i=1; i<n-1; i++){ for(int j=1; j<m-1; j++){ int l = left[i][j], r = right[i][j], u = up[i][j], d = down[i][j]; if(l == -1 or r == m or u == -1 or d == n) continue; if( u == stup.query(u+1, d, l+1, r) and r == stright.query(u+1, d, l+1, r) and l == stleft.query(u+1, d, l+1, r) and d == stdown.query(u+1, d, l+1, r) ) grind.push_back({l, r, u, d}); // cerr << i << " " << j << endl; // cerr << l << " " << r << " " << u << " " << d << endl; // cerr << stleft.query(u+1, d, l+1, r) << " " << stright.query(u+1, d, l+1, r) << " " << stup.query(u+1, d, l+1, r) << " " << stdown.query(u+1, d, l+1, r) << endl; } } // for(int i=0; i<n; i++){ // for(int j=0; j<m; j++){ // cout << left[i][j] << " "; // } // cout << endl; // } sort(grind.begin(), grind.end()); return unique(grind.begin(), grind.end()) - grind.begin(); } /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣠⣤⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⡴⡖⣻⡟⣛⡛⣿⣿⣿⣿⣻⣿⣿⡟⠛⠳⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣯⣾⣤⣹⣷⣿⣿⡿⣿⡿⣿⣿⣿⣿⣼⣧⣄⣚⠉⠛⠶⢶⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣙⠾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢘⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⠿⠛⠛⠛⠛⠿⠿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⡿⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⣿⣿⣯⡿⠀⠀⠀⠀⠀⠀⠀⠠⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢀⣀⣄⡀⠀⠀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⡇⣠⣾⣿⣿⣶⣶⣶⣶⣿⣦⡀⠀⠻⣤⣶⣾⣿⣿⣿⣿⣿⠿⠿⣿⣶⣄⠈⣿⡇⢹⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⠁⡿⠟⣉⣽⣿⣿⣿⣿⣿⣿⡗⠀⠀⢈⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣦⣹⡇⣽⣿⣿⣿⣿⣿⣿⣿⠀⣀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⢀⠴⠂⠀⣀⣤⣾⣿⣿⣿⣿⣿⡿⠀⢱⣿⣿⣏⣛⣛⣣⢬⣹⢿⠏⠀⢀⣼⣿⣯⡛⠒⢽⣿⣥⡿⣿⣿⣿⣿⣿⣿⣇⣿⣿⣿⣿⣿⣿⣿⣍⣉⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⣰⣿⠤⣶⣿⠿⣻⣿⣿⣿⣿⣿⣿⡇⠀⠀⠋⠀⠉⠉⠁⠒⠉⠀⠀⡀⠀⠀⢿⣿⣿⠛⠦⠀⠀⢸⡿⠋⠋⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡛⣆⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠈⠉⠉⢡⣰⣥⠾⣿⣿⣿⣿⣿⣿⣿⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠁⠀⠀⢸⡿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⣿⣿⡹⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⢀⡕⠽⣾⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣶⣶⣤⣶⣿⣷⣼⣧⡀⠀⠀⠀⠠⠀⢀⣰⣿⣿⣿⣿⣿⣿⣷⣻⣿⣿⣿⣿⣿⣿⢿⣿⣶⠄ ⠀⠀⠀⠀⠀⠀⠀⠀⡞⠀⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⢠⠎⠻⠯⣍⠙⠟⢻⣿⠿⣿⠟⠀⠀⠀⣶⣦⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⠳⣌⢣⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⣡⠖⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⠀⠈⠀⢀⣴⣿⠟⠁⢾⣿⣷⣄⡀⡀⠀⠀⠿⠟⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠈⠁⠀⣧ ⠀⠀⠀⠀⠀⠀⠀⣼⠃⠀⠀⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡤⠀⠀⠀⣠⣾⣾⠟⢛⣁⣤⣠⣼⣿⣿⣿⣿⣿⣶⣄⣠⣾⣫⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠙⠷⣦⣾⣿⠟⢿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⣱⠀⣼⣿⡯⡿⠾⠛⠛⠛⠛⠛⢻⣿⣿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠋⠀⠀⣻⣿⣿⣿⣿⣿⣿⣿⣷⣿⣷⠃⢿⡟⠀⠀⠰⣦⣤⣤⣴⣶⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⡶⢿⣷⣦⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠈⠀⠀⠀⠀⠀⠛⠉⠛⠛⠛⠻⣿⢟⣉⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠘⣼⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⣽⣷⡶⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⡇⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣷⣶⣠⣤⣠⣦⡡⣠⣼⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⠦⣽⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⠉⡆⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠿⠟⠛⠉⢿⣿⣿⣿⣿⣿⣿⣿⣿⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣟⡿⣻⣿⠟⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⠴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣟⡛⠁⠘⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢀⣀⣀⣀⣀⣀⣤⢴⣾⠿⣉⣽⠞⠁⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣻⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⡿⠒⠾⣿⣭⣌⡉⠉⠙⠳⠟⢁⣐⠛⠃⠀⢐⡶⠉⠉⠻⣿⣿⣿⣿⣯⡙⢿⣯⣉⠉⠻⣿⣿⣏⢿⣿⣿⣿⣿⣿⣬⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣧⢐⡦⣌⠙⢮⡹⠛⢶⣤⣶⣯⣍⢰⠋⠄⠘⠁⠀⠀⠀⠈⠍⠛⠻⢿⣿⣷⣍⡻⣿⣶⣮⣙⠿⢾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣿⣿⠆⣈⠵⠶⠈⢺⡉⠙⠿⣿⣿⣿⣷⡷⠂⠀⠀⠀⠰⣾⡄⢀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⢿⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣍⣽⣿⡜⣆⠳⣯⡲⣤⣀⠀⠀⠀⠀⠀⠀⠀ ⣿⣿⡌⡄⠀⠀⠀⠀⠙⢶⣄⠀⠙⢿⣿⣟⣀⠀⠀⠀⠀⠈⢿⣾⡇⠀⠀⠀⣮⢙⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣛⣿⣿⣿⣿⣿⣿⣿⣿⡿⠉⢿⡀⠀⠙⢿⣎⢿⣿⣶⣤⣀⠀⠀⠀ ⣿⣿⣷⡹⠀⠀⠀⠀⠀⠀⠈⠻⢦⣄⡙⢻⣿⣾⣤⡀⠀⠀⠈⢿⣿⡀⠀⠀⠹⣾⠟⣿⣿⣿⣿⣿⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⠿⡛⠑⠀⠂⠸⡿⠝⠀⠄⢻⣧⢻⣆⠉⡹⠿⣿⡂ ⣿⣿⣿⣏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢻⣿⣿⣿⣿⣷⣄⣀⠈⣿⣷⣄⠀⠘⠙⠰⢿⣿⣿⣿⣿⣿⣿⣧⣚⣿⣿⣯⡋⠄⠰⢉⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣧⢻⣦⠘⡇⠈⠛ ⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠈⠉⠙⠛⠛⠻⠾⣿⣿⣟⣷⠀⠀⢪⠙⢿⣿⣿⢿⣿⣿⠙⢻⣿⣿⠁⠶⠔⠈⢑⠋⠀⠀⠀⠀⠀⡀⠀⠀⢿⣿⣧⣙⠦⢻⡀⠀ ⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⡆⠀⠘⠷⣷⣧⣽⣾⣯⣿⡗⠸⣿⣿⠀⠠⢰⠚⠊⠀⠂⠀⠀⠀⠀⡌⠈⠒⠘⡿⡁⢹⣶⣾⡇⠀ ⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡇⢀⠀⠀⠸⡏⡿⢷⣜⢿⡇⠀⣿⣿⡀⠆⢀⠀⠂⠀⠀⡀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⢿⡿⠁⠀ ⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣆⠀⠀⠀⠁⠀⠀⠙⣿⡇⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠈⠂⠀⠐⠁⠀⠀⠀⠀⠀⠀⢸⠅⠀⠀ ⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠿⣦⡀⠀⠀⠀⠀⠀⠃⣿⠀⣿⣿⡇⢀⠀⠀⠀⠀⠀⠀⠀⠘⠆⠀⠀⠀⠀⠀⠀⠀⡸⣦⠀⢀ ⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⡄⠀⣸⣿⡄⠀⡏⠀⢿⢿⡇⠀⠄⠀⠀⠘⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⡄⠀⠀⣿⣿⣿ ⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⡀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⡀⠀⠀⠙⡽⢣⡜⠐⠹⠆⠁⠀⢺⣿⡇⠀⠀⠀⠀⠀⠀⢡⡂⠐⠀⠂⢤⡀⠈⠀⠀⠀⢀⣿⣿⣿ */

Compilation message (stderr)

rect.cpp: In constructor 'segment::segment(std::vector<int>&)':
rect.cpp:12:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
      |                ~^~~~~~~~~
rect.cpp: In constructor 'segment2d::segment2d(std::vector<std::vector<int> >&)':
rect.cpp:36:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0; i<v.size(); i++) tr[i+sz] = segment(v[i]);
      |                ~^~~~~~~~~
rect.cpp: In constructor 'segment2::segment2(std::vector<int>&)':
rect.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
      |                ~^~~~~~~~~
rect.cpp: In constructor 'segment22d::segment22d(std::vector<std::vector<int> >&)':
rect.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]);
      |                ~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:173:6: warning: unused variable 'ans' [-Wunused-variable]
  173 |  int ans = 0;
      |      ^~~
#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...