Submission #154445

#TimeUsernameProblemLanguageResultExecution timeMemory
154445crackersamdjamRectangles (IOI19_rect)C++14
Compilation error
0 ms0 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse4,popcnt,abm,mmx,tune=native") #include <bits/stdc++.h> #define gc getchar_unlocked() #define pc(x) putchar_unlocked(x) template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;} template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);} template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);} template<typename T> void print(T n){printn(n);pc(10);} template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);} using namespace std; const int MM = 2502; int n, m, ans; int first[MM], last[MM], bit[MM]; stack<pair<int, int>> st; map<int, int, greater<int>> hor[MM][MM], vert[MM][MM]; //stores either right or down endpoint, and "dp" val void update(int i, int v){ for(i = MM-1-i; i < MM; i += i&-i) bit[i] += v; } int query(int i){ int ret = 0; for(i = MM-1-i; i; i -= i&-i) ret += bit[i]; return ret; } void clear(){ while(!st.empty()) st.pop(); } vector<pair<int, int>> vec(MM); vector<int> unupdate; long long count_rectangles(vector<vector<int>> a){ n = a.size(), m = a[0].size(); for(int i = 0; i < n; i++){ clear(); for(int j = 0; j < m; j++){ //help remove duplicate while(!st.empty() && st.top().first < a[i][j]) st.pop(); first[j] = (st.empty() || st.top().first == a[i][j]) ? -1 : st.top().second; st.push({a[i][j], j}); } clear(); for(int j = m-1; j >= 0; j--){ while(!st.empty() && st.top().first <= a[i][j]) st.pop(); last[j] = st.empty() ? -1 : st.top().second; st.push({a[i][j], j}); } for(int j = 0; j < m; j++){ if(first[j] == -1 || last[j] == -1) continue; first[j]++, last[j]--; hor[i][first[j]][last[j]] = 1; } } for(int j = 0; j < m; j++){ clear(); for(int i = 0; i < n; i++){ //help remove duplicate while(!st.empty() && st.top().first < a[i][j]) st.pop(); first[i] = (st.empty() || st.top().first == a[i][j]) ? -1 : st.top().second; st.push({a[i][j], i}); } clear(); for(int i = n-1; i >= 0; i--){ while(!st.empty() && st.top().first <= a[i][j]) st.pop(); last[i] = st.empty() ? -1 : st.top().second; st.push({a[i][j], i}); } for(int i = 0; i < n; i++){ if(first[i] == -1 || last[i] == -1) continue; first[i]++, last[i]--; vert[first[i]][j][last[i]] = 1; } } for(int i = n-1; i >= 0; i--){ for(int j = m-1; j >= 0; j--){ for(auto &x: hor[i][j]) if(hor[i+1][j].count(x.first)) x.second += hor[i+1][j][x.first]; for(auto &x: vert[i][j]) if(vert[i][j+1].count(x.first)) x.second += vert[i][j+1][x.first]; for(int x: unupdate) update(x, -1); unupdate.clear(); vec.clear(); for(auto &x: hor[i][j]) vec.push_back({x.first-j+1, x.second}); //adjust sort(vec.begin(), vec.end(), [](auto &x, auto &y){ return x.second > y.second; }); //now sorted by y //printf("go "); print(i, j); int l = 0; for(auto &b: vert[i][j]){ int bf = b.first-i+1; while(l < vec.size() && bf <= vec[l].second){ unupdate.push_back(vec[l].first); update(vec[l++].first, 1); //printf("up "); print(vec[l++].first); } ans += query(b.second); //printf("q "); print(b.second, query(b.second)); } //if(x.first-j+1 <= y.second && y.first-i+1 <= x.second) /* * sort hor and vert by y reversed * loop through vert with l ptr for hor * while hor[l].y >= vert.y, push hor[l++].x into bit * answer += query_greater_than_equals(vert[i].x) */ //okay so //print(i, j, hor[i][j].size(), vert[i][j].size()); /* for(auto &x: hor[i][j]){ for(auto &y: vert[i][j]){ if(x.first-j+1 <= y.second && y.first-i+1 <= x.second){ ans++; //print(-1, i, j, y.first, x.first); } } } */ } } return ans; } #ifndef ONLINE_JUDGE int main(){ //print(count_rectangles({{3, 2, 2, 3}})); print(count_rectangles({{4, 8, 7, 5, 6}, {7, 4, 10, 3, 5}, {9, 7, 20, 14, 2}, {9, 14, 7, 3, 6}, {5, 7, 5, 2, 7}, {4, 5, 13, 5, 6}}) ); return 0; } #endif /* * in a row, for every point, get 1st left > and 1st right greater * this will get all possible * * using mono stack * * * sort row segments * starting at point i, on row j * for each (i, r), dp for how long can go down * * then do same for vertical * * when it works is when: vert_seg <= dp_vert[hor_seg] and hor_seg <= dp_hor[vert_seg] * * sort hor and vert by y reversed * loop through vert with l ptr for hor * while hor[l] >= y, push hor[l++].x into bit * answer += query_greater_than_equals(vert[i].x) * * vertical <= NM * horizontal <= NM * time complexity vert * log(hor) = NM log(NM) */

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:128:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l < vec.size() && bf <= vec[l].second){
                       ~~^~~~~~~~~~~~
/tmp/ccB5O1oE.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cckK3ESh.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status