oj.uz

Submission #144533

# Submission time Handle Problem Language Result Execution time Memory
144533 2019-08-17T05:06:26 Z shdut Rectangles (IOI19_rect) C++14
10 / 100
 5000 ms 846508 KB 
#include "rect.h"
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;

#define inf 1000000007
#define SZ(x) x.size()
#define all(x) x.begin(), x.end()
#define N 2505
#define pb push_back
#define x first
#define y second
#define ls p<<1
#define rs p<<1|1
#define vi std::vector<int>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b - 1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";

int U[N][N], L[N][N], q[N];
vi H[N][N], W[N][N];
unordered_map<int,int>g[N][N];
int solve(std::vector<std::vector<int> > &a, int f1 = 0, int f2 = 0){
    int ans = 0;
    int n = SZ(a), m = SZ(a[0]), k;
    //for(auto &o : a){
    //    for(auto &x : o)cerr << x << " ";
    //    cerr << "\n";
    //}
    rep(i, 0, m)rep(j, 0, m)W[i][j].clear();
    rep(i, 0, n)rep(j, 0, n)H[i][j].clear();
    rep(i, 0, n){
        int t = 0;
        rep(j, 0, m){
            while(t && a[i][q[t-1]] < a[i][j])t--;
            L[i][j] = t == 0 ? -1 : q[t-1];
            if(t){
                k = j - q[t-1];
                W[k][j].pb(i);
                //cerr << q[t-1] << " " << j << " " << i << " ..\n";
            }
            q[t++] = j;
        }
        t = 0;
        per(j, 0, m){
            while(t && a[i][q[t-1]] < a[i][j])t--;
            if(t){
                k = q[t-1] - j;
                if(W[k][q[t-1]].empty() || W[k][q[t-1]].back() != i){
                    W[k][q[t-1]].pb(i);
                    //cerr << j << " " << q[t-1] << " " <<  i << " ..\n";
                }
            }
            q[t++] = j;
        }
    }
    rep(j, 0, m){
        int t = 0;
        rep(i, 0, n){
            while(t && a[q[t-1]][j] < a[i][j])t--;
            U[i][j] = t == 0 ? -1 : q[t-1];
            if(t){
                k = i - q[t-1];
                H[k][i].pb(j);
                //cerr << q[t-1] << " " << i << " " << j << " ,,\n";
            }
            q[t++] = i;
        }
        t = 0;
        per(i, 0, n){
            while(t && a[q[t-1]][j] < a[i][j])t--;
            if(t){
                k = q[t-1] - i;
                if(H[k][q[t-1]].empty() || H[k][q[t-1]].back() != j){
                    H[k][q[t-1]].pb(j);
                    //cerr << i << " " << q[t-1] << " " <<  j << " ,,\n";
                }
            }
            q[t++] = i;
        }
    }
    rep(i, 2, n){
        rep(j, 1, m-1){
            int w = L[i-1][j+1], h = U[i][j];
            if(w < 0 || h < 0)continue;
            w = j + 1 - w;
            h = i - h;
            if(w < 2 || h < 2)continue;
            int y = upper_bound(all(W[w][j+1]), i-1) - lower_bound(all(W[w][j+1]), i-h+1);
            if(y < h-1)continue;
            int x = upper_bound(all(H[h][i]), j) - lower_bound(all(H[h][i]), j-w+2);
            if(x < w-1)continue;
            x = i-h+1, y = j+1-w+1;
            if(f1)x = n-1-x;
            if(f2)y = m-1-y;
            int x1 = i-1, y1 = j;
            if(f1)x1 = n-1-x1;
            if(f2)y1 = m-1-y1;
            if(x1 > x)swap(x, x1);
            if(y1 > y)swap(y, y1);
            int id = x1 * m + y1;
            if(g[x][y].count(id) == 0){
                g[x][y][id] = 1;
                ans++;
                //cerr << i << " " << j << "\n";
                //cerr << j+1-w+1 << " " << j << " , " << i-h+1 << " " << i-1 << "\n";
                //cerr << x1 << " " << y1 << ","  << x << " " << y << "\n";
            }
        }
    }
    //DBG(ans)
    return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n = SZ(a), m = SZ(a[0]);
    long long ans = 0;
    rep(i, 0, n)rep(j, 0, m)g[i][j].clear();
    rep(x, 0, 2){
        rep(y, 0, 2){
            ans += solve(a, x, y);
            rep(j, 0, m/2)rep(i, 0, n)swap(a[i][j], a[i][m-1-j]);
        }
        rep(i, 0, n/2)rep(j, 0, m)swap(a[i][j], a[n-1-i][j]);
    }
    return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 638968 KB Output is correct
2 Correct 658 ms 639308 KB Output is correct
3 Correct 723 ms 639288 KB Output is correct
4 Correct 626 ms 639424 KB Output is correct
5 Correct 620 ms 639196 KB Output is correct
6 Incorrect 618 ms 639224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 638968 KB Output is correct
2 Correct 658 ms 639308 KB Output is correct
3 Correct 723 ms 639288 KB Output is correct
4 Correct 626 ms 639424 KB Output is correct
5 Correct 620 ms 639196 KB Output is correct
6 Incorrect 618 ms 639224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 638968 KB Output is correct
2 Correct 658 ms 639308 KB Output is correct
3 Correct 723 ms 639288 KB Output is correct
4 Correct 626 ms 639424 KB Output is correct
5 Correct 620 ms 639196 KB Output is correct
6 Incorrect 618 ms 639224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 638968 KB Output is correct
2 Correct 658 ms 639308 KB Output is correct
3 Correct 723 ms 639288 KB Output is correct
4 Correct 626 ms 639424 KB Output is correct
5 Correct 620 ms 639196 KB Output is correct
6 Incorrect 618 ms 639224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 639396 KB Output is correct
2 Correct 697 ms 639480 KB Output is correct
3 Correct 714 ms 639160 KB Output is correct
4 Correct 618 ms 638940 KB Output is correct
5 Correct 716 ms 639708 KB Output is correct
6 Correct 727 ms 639452 KB Output is correct
7 Correct 724 ms 639608 KB Output is correct
8 Correct 720 ms 639500 KB Output is correct
9 Correct 734 ms 639408 KB Output is correct
10 Correct 716 ms 639144 KB Output is correct
11 Correct 722 ms 639480 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 638948 KB Output is correct
2 Correct 2999 ms 739384 KB Output is correct
3 Execution timed out 5158 ms 846508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 638968 KB Output is correct
2 Correct 658 ms 639308 KB Output is correct
3 Correct 723 ms 639288 KB Output is correct
4 Correct 626 ms 639424 KB Output is correct
5 Correct 620 ms 639196 KB Output is correct
6 Incorrect 618 ms 639224 KB Output isn't correct
7 Halted 0 ms 0 KB -