제출 #430013

#제출 시각아이디문제언어결과실행 시간메모리
430013egekabasRectangles (IOI19_rect)C++14
0 / 100
24 ms25816 KiB
#include "rect.h" #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<int, int> pii; typedef pair<ld, ld> pld; int bit[2509][2509]; int bitsz; void upd(int x, int y, int val){ for(int i1 = x+1; i1 > 0; i1 -= i1&(-i1)) for(int i2 = y+1; i2 <= bitsz; i2 += i2&(-i2)) bit[i1][i2] += val; } int get(int x, int y){ int ret = 0; for(int i1 = x+1; i1 <= bitsz; i1 += i1&(-i1)) for(int i2 = y+1; i2 > 0; i2 -= i2&(-i2)) ret += bit[i1][i2]; return ret; } ll pickdouble(int n){ return ll(n)*(n+1)/2; } long long count_rectangles(std::vector<std::vector<int> > a) { int n = a.size(), m = a[0].size(); bitsz = max(n, m); for(int i = 1; i <= bitsz; ++i) for(int j = 1; j <= bitsz; ++j) bit[i][j] = 0; vector<set<pii>> pos(n); for(int i = 0; i < n; ++i){ vector<int> cur; for(int j = m-1; j >= 0; --j){ while(cur.size() && a[i][cur.back()] < a[i][j]){ pos[i].insert({j, cur.back()}); cur.pop_back(); } if(cur.size()) pos[i].insert({j, cur.back()}); cur.pb(j); } } vector<vector<pair<pii, int>>> maxval(m); for(int i = 0; i < n; ++i) for(auto u : pos[i]){ int j; for(j = i+1; j < n; ++j){ auto it = pos[j].lower_bound(u); if(it == pos[j].end() || *it != u) break; pos[j].erase(it); } --j; if(u.ss-u.ff > 1) maxval[u.ff].pb({{i, j}, u.ss}); //cout << u.ff << ' ' << u.ss << ' ' << i << ' ' << j << '\n'; } pos = vector<set<pii>>(m); for(int i = 0; i < m; ++i){ vector<int> cur; for(int j = n-1; j >= 0; --j){ while(cur.size() && a[cur.back()][i] < a[j][i]){ pos[i].insert({j, cur.back()}); cur.pop_back(); } if(cur.size()) pos[i].insert({j, cur.back()}); cur.pb(j); } } vector<vector<pair<pii, int>>> fin(m); for(int i = 0; i < m; ++i) for(auto u : pos[i]){ int j; for(j = i+1; j < m; ++j){ auto it = pos[j].lower_bound(u); if(it == pos[j].end() || *it != u) break; pos[j].erase(it); } --j; if(u.ss-u.ff > 1) for(int k = i; k <= j; ++k) fin[k].pb({{u.ff, u.ss}, j}); } ll ans = 0; for(int i = 1; i < m; ++i){ sort(all(fin[i])); int curidx = 0; for(auto u : fin[i]){ while(curidx < maxval[i-1].size() && maxval[i-1][curidx].ff.ff <= u.ff.ff+1){ upd(maxval[i-1][curidx].ff.ss, maxval[i-1][curidx].ss, 1); ++curidx; } int val = get(u.ff.ss-1, u.ss+1); //cout << i << ' ' << u.ss << ' ' << u.ff.ff << ' ' << u.ff.ss << ' ' << val << '\n'; ans += val; } for(auto u : maxval[i-1]) upd(u.ff.ss, u.ss, -1); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    while(curidx < maxval[i-1].size() && maxval[i-1][curidx].ff.ff <= u.ff.ff+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...