제출 #157358

#제출 시각아이디문제언어결과실행 시간메모리
157358qkxwsmRectangles (IOI19_rect)C++14
72 / 100
3729 ms1048576 KiB
#include "rect.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define y1 qkx #define y2 wsm #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) #define SZ(x) ((int) (x).size()) #define ALL(x) (x).begin(), (x).end() #define INF 1000000007 #define MAXN 2513 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; int N, M; vector<short> ev[MAXN][MAXN], eh[MAXN][MAXN], dv[MAXN][MAXN], dh[MAXN][MAXN]; ll ans; ll count_rectangles(vector<vi> a) { N = SZ(a); M = SZ(a[0]); FOR(i, 0, N) { vpi cand; cand.PB({INF, M + 1}); FORD(j, M, 0) { while(cand.back().fi < a[i][j]) cand.pop_back(); short idx = cand.back().se; if (idx < M && idx != j + 1) { eh[i][j + 1].PB(idx - 1); } cand.PB({a[i][j], j}); } cand.clear(); cand.PB({INF, -2}); FOR(j, 0, M) { while(cand.back().fi < a[i][j]) cand.pop_back(); short idx = cand.back().se; if (idx >= 0 & idx != j - 1) { eh[i][idx + 1].PB(j - 1); } cand.PB({a[i][j], j}); } } FOR(i, 0, M) { vpi cand; cand.PB({INF, N + 1}); FORD(j, N, 0) { while(cand.back().fi < a[j][i]) cand.pop_back(); short idx = cand.back().se; if (idx < N && idx != j + 1) { ev[j + 1][i].PB(idx - 1); } cand.PB({a[j][i], j}); } cand.clear(); cand.PB({INF, -2}); FOR(j, 0, N) { while(cand.back().fi < a[j][i]) cand.pop_back(); short idx = cand.back().se; if (idx >= 0 && idx != j - 1) { ev[idx + 1][i].PB(j - 1); } cand.PB({a[j][i], j}); } } //log factor here. FOR(i, 0, N) { FOR(j, 0, M) { sort(ALL(ev[i][j])); ev[i][j].erase(unique(ALL(ev[i][j])), ev[i][j].end()); sort(ALL(eh[i][j])); eh[i][j].erase(unique(ALL(eh[i][j])), eh[i][j].end()); dv[i][j].resize(SZ(ev[i][j])); dh[i][j].resize(SZ(eh[i][j])); } } FOR(i, 0, N) { FORD(j, M, 0) { int idx = 0; FOR(k, 0, SZ(ev[i][j])) { dv[i][j][k] = j; int x = ev[i][j][k]; while(idx < SZ(ev[i][j + 1]) && ev[i][j + 1][idx] < x) idx++; if (idx >= SZ(ev[i][j + 1]) || ev[i][j + 1][idx] != x) continue; dv[i][j][k] = dv[i][j + 1][idx]; } } } FOR(i, 0, M) { FORD(j, N, 0) { int idx = 0; FOR(k, 0, SZ(eh[j][i])) { dh[j][i][k] = j; int y = eh[j][i][k]; while(idx < SZ(eh[j + 1][i]) && eh[j + 1][i][idx] < y) idx++; if (idx >= SZ(eh[j + 1][i]) || eh[j + 1][i][idx] != y) continue; dh[j][i][k] = dh[j + 1][i][idx]; } } } //log factor here too. FOR(i, 1, N - 1) { FOR(j, 1, M - 1) { vpi ps; FOR(k, 0, SZ(eh[i][j])) { ps.PB({dh[i][j][k], eh[i][j][k]}); } sort(ALL(ps)); ordered_set<pii> ord; FOR(k, 0, SZ(ps)) { ord.insert({ps[k].se, k}); } int iter = 0; FOR(k, 0, SZ(ev[i][j])) { while(iter < SZ(ps) && ps[iter].fi < ev[i][j][k]) { ord.erase({ps[iter].se, iter}); iter++; } ans += ord.order_of_key({dv[i][j][k], INF}); } ord.clear(); } } return ans; }

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

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:72:12: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
    if (idx >= 0 & idx != j - 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...