oj.uz

Submission #144277

# Submission time Handle Problem Language Result Execution time Memory
144277 2019-08-16T13:26:20 Z shdut Rectangles (IOI19_rect) C++14
0 / 100
 10 ms 10488 KB 
#include "rect.h"
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

#define inf 1000000007
#define SZ(x) x.size()
#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 DBG(x) cerr << (#x) << "=" << x << "\n";

int U[N][N], L[N][N], q[N], T[N], H[N], Q[N][N];
long long count_rectangles(std::vector<std::vector<int> > a) {
    //for(auto &o : a){
    //    for(auto &x : o)cerr << x << " ";
    //    cerr << "\n";
    //}
    int n = SZ(a), m = SZ(a[0]);
    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 ? 0 : q[t-1];
            //cerr << L[i][j] << " ";
            q[t++] = j;
        }
        //cerr << "\n";
    }
    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 ? 0 : q[t-1];
            //cerr << U[i][j] << " ";
            q[t++] = i;
        }
        //cerr << "\n";
    }
    rep(i, 0, m)H[i] = T[i] = 0;
    long long ans = 0;
    rep(i, 0, n){
        int t = 0;
        rep(j, 0, m-1){
            while(t && U[i][q[t-1]] <= U[i][j])t--;
            q[t++] = j;
            int k = j+1;
            //DBG(U[i][j])
            //while(H[k] < T[k] && Q[k][H[k]] <= U[i][j]){
            //    H[k]++;
            //}
            if(i >=2 && j){
                int x = t-1, y = 0, w = L[i-1][k];
                while(y < T[k] && Q[k][y] <= U[i][j])y++;
                //cerr << i << " " << j << ":\n";
                //cerr << q[x] << " " << Q[k][y] << " " << U[i][q[x]] << ", " << L[Q[k][y]][k] << "\n"; 
                while(x >= 0 && q[x] > w){
                    while(y < T[j] && Q[k][y] <= U[i][q[x]])y++;
                    while(y < T[j] && L[Q[k][y]][k] >= q[x])y++;
                    if(y == T[k])break;
                    int z = y == 0 ? 1 : Q[k][y-1] + 1;
                    //cerr << z << " " << i << ", " << q[x] << " " << j << "\n";
                    ans += (j - q[x] + 1) * max(i - z, 0);
                    x--;
                }
            }
        }
        rep(j, 0, m){
            while(H[j] < T[j] && L[Q[j][T[j]-1]][j] <= L[i][j])T[j]--;
            Q[j][T[j]++] = i;
        }
    }
    return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 10488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -