oj.uz

답안 #296633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
296633 2020-09-10T17:45:46 Z Osama_Alkhodairy Rectangles (IOI19_rect) C++17
100 / 100
 3832 ms 856724 KB 
#include <bits/stdc++.h>
#include "rect.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

const int N = 2501;
const int INF = (int)1e9;

struct segment{
    vector <int> tree;
    int n;
    void build(vector <int> &a, int b){
        n = a.size();
        tree.resize(2 * n, -INF);
        for(int i = 0 ; i < n ; i++){
            if(a[i] != -1) tree[i + n] = a[i] * b;
        }
        for(int i = n - 1 ; i > 0 ; i--){
            tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
        }
    }
    int query(int l, int r){
        r++;
        int ret = -INF;
        for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
            if(l & 1) ret = max(ret, tree[l++]);
            if(r & 1) ret = max(ret, tree[--r]);
        }
        return ret;
    }
};

int n, m, vis[N * N];
vector <vector <int> > a;
vector <vector <int> > us, rs, ds, ls, ue, re, de, le;
vector <segment> ue_tree, re_tree, de_tree, le_tree;
vector <int> v[N * N];

vector <int> calc(vector <int> &a, int b, int c){
    //~ b = 0 for >
    //~ b = 1 for >=
    //~ c = 0 for forward
    //~ c = 1 for backward
    int n = a.size();
    vector <int> inds;
    for(int i = 0 ; i < n ; i++){
        if(c == 0) inds.push_back(i);
        else inds.push_back(n - i - 1);
    }
    vector <int> ret(n);
    vector <int> cur;
    for(auto &i : inds){
        while(cur.size() && a[i] >= a[cur.back()] + b){
            cur.pop_back();
        }
        if(cur.size() == 0) ret[i] = -1;
        else ret[i] = cur.back();
        cur.push_back(i);
    }
    return ret;
}
void add(int r1, int c1, int r2, int c2){
    if(r1 == -1 || c1 == -1 || r2 == -1 || c2 == -1) return;
    v[r1 * m + c1].push_back(r2 * m + c2);
}
bool check(int r1, int c1, int r2, int c2){
    int v = -de_tree[r1].query(c1 + 1, c2 - 1);
    if(v < r2) return 0;
    v = ue_tree[r2].query(c1 + 1, c2 - 1);
    if(v > r1) return 0;
    v = -re_tree[c1].query(r1 + 1, r2 - 1);
    if(v < c2) return 0;
    v = le_tree[c2].query(r1 + 1, r2 - 1);
    if(v > c1) return 0;
    return 1;
}
long long count_rectangles(std::vector<std::vector<int> > A) {
    a = A;
    n = a.size();
    m = a[0].size();
    us.resize(n, vector <int>(m));
    ue.resize(n, vector <int>(m));
    ds.resize(n, vector <int>(m));
    de.resize(n, vector <int>(m));
    ls.resize(n, vector <int>(m));
    le.resize(n, vector <int>(m));
    rs.resize(n, vector <int>(m));
    re.resize(n, vector <int>(m));
    ue_tree.resize(n);
    de_tree.resize(n);
    le_tree.resize(m);
    re_tree.resize(m);
    for(int i = 0 ; i < n ; i++){
        vector <int> cur = a[i];
        ls[i] = calc(cur, 0, 0);
        le[i] = calc(cur, 1, 0);
        rs[i] = calc(cur, 0, 1);
        re[i] = calc(cur, 1, 1);
    }
    for(int j = 0 ; j < m ; j++){
        vector <int> cur(n);
        for(int i = 0 ; i < n ; i++){
            cur[i] = a[i][j];
        }
        vector <int> g;
        g = calc(cur, 0, 0);
        for(int i = 0 ; i < n ; i++){
            us[i][j] = g[i];
        }
        g = calc(cur, 1, 0);
        for(int i = 0 ; i < n ; i++){
            ue[i][j] = g[i];
        }
        g = calc(cur, 0, 1);
        for(int i = 0 ; i < n ; i++){
            ds[i][j] = g[i];
        }
        g = calc(cur, 1, 1);
        for(int i = 0 ; i < n ; i++){
            de[i][j] = g[i];
        }
    }
    for(int i = 0 ; i < n ; i++){
        ue_tree[i].build(ue[i], 1);
        de_tree[i].build(de[i], -1);
    }
    for(int j = 0 ; j < m ; j++){
        vector <int> cur(n);
        for(int i = 0 ; i < n ; i++){
            cur[i] = le[i][j];
        }
        le_tree[j].build(cur, 1);
        cur.assign(n, 0);
        for(int i = 0 ; i < n ; i++){
            cur[i] = re[i][j];
        }
        re_tree[j].build(cur, -1);
    }
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            add(us[i][j], ls[i][j], ds[i][j], rs[i][j]);
        }
    }
    int ret = 0;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            for(auto &k : v[i * m + j]){
                if(vis[k]) continue;
                vis[k] = 1;
                ret += check(i, j, k / m, k % m);
            }
            for(auto &k : v[i * m + j]){
                vis[k] = 0;
            }
        }
    }
    return ret;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 147192 KB Output is correct
2 Correct 100 ms 147320 KB Output is correct
3 Correct 100 ms 147324 KB Output is correct
4 Correct 101 ms 147320 KB Output is correct
5 Correct 100 ms 147260 KB Output is correct
6 Correct 100 ms 147296 KB Output is correct
7 Correct 99 ms 147192 KB Output is correct
8 Correct 101 ms 147192 KB Output is correct
9 Correct 99 ms 147304 KB Output is correct
10 Correct 100 ms 147320 KB Output is correct
11 Correct 99 ms 147320 KB Output is correct
12 Correct 110 ms 147320 KB Output is correct
13 Correct 98 ms 147192 KB Output is correct
14 Correct 98 ms 147192 KB Output is correct
15 Correct 99 ms 147192 KB Output is correct
16 Correct 100 ms 147192 KB Output is correct
17 Correct 103 ms 147324 KB Output is correct
18 Correct 101 ms 147192 KB Output is correct
19 Correct 101 ms 147320 KB Output is correct
20 Correct 99 ms 147192 KB Output is correct
21 Correct 99 ms 147192 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 147192 KB Output is correct
2 Correct 100 ms 147320 KB Output is correct
3 Correct 100 ms 147324 KB Output is correct
4 Correct 101 ms 147320 KB Output is correct
5 Correct 100 ms 147260 KB Output is correct
6 Correct 100 ms 147296 KB Output is correct
7 Correct 99 ms 147192 KB Output is correct
8 Correct 101 ms 147192 KB Output is correct
9 Correct 99 ms 147304 KB Output is correct
10 Correct 100 ms 147320 KB Output is correct
11 Correct 99 ms 147320 KB Output is correct
12 Correct 110 ms 147320 KB Output is correct
13 Correct 98 ms 147192 KB Output is correct
14 Correct 98 ms 147192 KB Output is correct
15 Correct 99 ms 147192 KB Output is correct
16 Correct 100 ms 147192 KB Output is correct
17 Correct 102 ms 148020 KB Output is correct
18 Correct 104 ms 147960 KB Output is correct
19 Correct 106 ms 147960 KB Output is correct
20 Correct 104 ms 147832 KB Output is correct
21 Correct 106 ms 147960 KB Output is correct
22 Correct 104 ms 147836 KB Output is correct
23 Correct 103 ms 147832 KB Output is correct
24 Correct 103 ms 147576 KB Output is correct
25 Correct 103 ms 147324 KB Output is correct
26 Correct 101 ms 147192 KB Output is correct
27 Correct 101 ms 147320 KB Output is correct
28 Correct 99 ms 147192 KB Output is correct
29 Correct 99 ms 147192 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 147192 KB Output is correct
2 Correct 100 ms 147320 KB Output is correct
3 Correct 100 ms 147324 KB Output is correct
4 Correct 101 ms 147320 KB Output is correct
5 Correct 100 ms 147260 KB Output is correct
6 Correct 100 ms 147296 KB Output is correct
7 Correct 99 ms 147192 KB Output is correct
8 Correct 101 ms 147192 KB Output is correct
9 Correct 99 ms 147304 KB Output is correct
10 Correct 100 ms 147320 KB Output is correct
11 Correct 99 ms 147320 KB Output is correct
12 Correct 110 ms 147320 KB Output is correct
13 Correct 98 ms 147192 KB Output is correct
14 Correct 98 ms 147192 KB Output is correct
15 Correct 99 ms 147192 KB Output is correct
16 Correct 100 ms 147192 KB Output is correct
17 Correct 102 ms 148020 KB Output is correct
18 Correct 104 ms 147960 KB Output is correct
19 Correct 106 ms 147960 KB Output is correct
20 Correct 104 ms 147832 KB Output is correct
21 Correct 106 ms 147960 KB Output is correct
22 Correct 104 ms 147836 KB Output is correct
23 Correct 103 ms 147832 KB Output is correct
24 Correct 103 ms 147576 KB Output is correct
25 Correct 122 ms 151764 KB Output is correct
26 Correct 119 ms 151800 KB Output is correct
27 Correct 119 ms 151800 KB Output is correct
28 Correct 119 ms 151032 KB Output is correct
29 Correct 120 ms 151288 KB Output is correct
30 Correct 119 ms 151516 KB Output is correct
31 Correct 120 ms 151288 KB Output is correct
32 Correct 123 ms 151416 KB Output is correct
33 Correct 103 ms 147324 KB Output is correct
34 Correct 101 ms 147192 KB Output is correct
35 Correct 101 ms 147320 KB Output is correct
36 Correct 99 ms 147192 KB Output is correct
37 Correct 99 ms 147192 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 147192 KB Output is correct
2 Correct 100 ms 147320 KB Output is correct
3 Correct 100 ms 147324 KB Output is correct
4 Correct 101 ms 147320 KB Output is correct
5 Correct 100 ms 147260 KB Output is correct
6 Correct 100 ms 147296 KB Output is correct
7 Correct 99 ms 147192 KB Output is correct
8 Correct 101 ms 147192 KB Output is correct
9 Correct 99 ms 147304 KB Output is correct
10 Correct 100 ms 147320 KB Output is correct
11 Correct 99 ms 147320 KB Output is correct
12 Correct 110 ms 147320 KB Output is correct
13 Correct 98 ms 147192 KB Output is correct
14 Correct 98 ms 147192 KB Output is correct
15 Correct 99 ms 147192 KB Output is correct
16 Correct 100 ms 147192 KB Output is correct
17 Correct 102 ms 148020 KB Output is correct
18 Correct 104 ms 147960 KB Output is correct
19 Correct 106 ms 147960 KB Output is correct
20 Correct 104 ms 147832 KB Output is correct
21 Correct 106 ms 147960 KB Output is correct
22 Correct 104 ms 147836 KB Output is correct
23 Correct 103 ms 147832 KB Output is correct
24 Correct 103 ms 147576 KB Output is correct
25 Correct 122 ms 151764 KB Output is correct
26 Correct 119 ms 151800 KB Output is correct
27 Correct 119 ms 151800 KB Output is correct
28 Correct 119 ms 151032 KB Output is correct
29 Correct 120 ms 151288 KB Output is correct
30 Correct 119 ms 151516 KB Output is correct
31 Correct 120 ms 151288 KB Output is correct
32 Correct 123 ms 151416 KB Output is correct
33 Correct 228 ms 186488 KB Output is correct
34 Correct 229 ms 186616 KB Output is correct
35 Correct 227 ms 186488 KB Output is correct
36 Correct 225 ms 186488 KB Output is correct
37 Correct 345 ms 199800 KB Output is correct
38 Correct 350 ms 200312 KB Output is correct
39 Correct 350 ms 200440 KB Output is correct
40 Correct 329 ms 196984 KB Output is correct
41 Correct 284 ms 190712 KB Output is correct
42 Correct 304 ms 192248 KB Output is correct
43 Correct 361 ms 194952 KB Output is correct
44 Correct 350 ms 195448 KB Output is correct
45 Correct 220 ms 171552 KB Output is correct
46 Correct 221 ms 171384 KB Output is correct
47 Correct 341 ms 193552 KB Output is correct
48 Correct 342 ms 194296 KB Output is correct
49 Correct 103 ms 147324 KB Output is correct
50 Correct 101 ms 147192 KB Output is correct
51 Correct 101 ms 147320 KB Output is correct
52 Correct 99 ms 147192 KB Output is correct
53 Correct 99 ms 147192 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 148128 KB Output is correct
2 Correct 107 ms 147960 KB Output is correct
3 Correct 105 ms 147960 KB Output is correct
4 Correct 104 ms 147324 KB Output is correct
5 Correct 105 ms 148088 KB Output is correct
6 Correct 104 ms 148012 KB Output is correct
7 Correct 105 ms 148088 KB Output is correct
8 Correct 104 ms 147960 KB Output is correct
9 Correct 104 ms 148088 KB Output is correct
10 Correct 100 ms 147704 KB Output is correct
11 Correct 105 ms 147832 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 147324 KB Output is correct
2 Correct 1244 ms 398240 KB Output is correct
3 Correct 2554 ms 690676 KB Output is correct
4 Correct 2570 ms 693444 KB Output is correct
5 Correct 2618 ms 693284 KB Output is correct
6 Correct 927 ms 378872 KB Output is correct
7 Correct 1592 ms 585628 KB Output is correct
8 Correct 1703 ms 614552 KB Output is correct
9 Correct 103 ms 147324 KB Output is correct
10 Correct 101 ms 147192 KB Output is correct
11 Correct 101 ms 147320 KB Output is correct
12 Correct 99 ms 147192 KB Output is correct
13 Correct 99 ms 147192 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 147192 KB Output is correct
2 Correct 100 ms 147320 KB Output is correct
3 Correct 100 ms 147324 KB Output is correct
4 Correct 101 ms 147320 KB Output is correct
5 Correct 100 ms 147260 KB Output is correct
6 Correct 100 ms 147296 KB Output is correct
7 Correct 99 ms 147192 KB Output is correct
8 Correct 101 ms 147192 KB Output is correct
9 Correct 99 ms 147304 KB Output is correct
10 Correct 100 ms 147320 KB Output is correct
11 Correct 99 ms 147320 KB Output is correct
12 Correct 110 ms 147320 KB Output is correct
13 Correct 98 ms 147192 KB Output is correct
14 Correct 98 ms 147192 KB Output is correct
15 Correct 99 ms 147192 KB Output is correct
16 Correct 100 ms 147192 KB Output is correct
17 Correct 102 ms 148020 KB Output is correct
18 Correct 104 ms 147960 KB Output is correct
19 Correct 106 ms 147960 KB Output is correct
20 Correct 104 ms 147832 KB Output is correct
21 Correct 106 ms 147960 KB Output is correct
22 Correct 104 ms 147836 KB Output is correct
23 Correct 103 ms 147832 KB Output is correct
24 Correct 103 ms 147576 KB Output is correct
25 Correct 122 ms 151764 KB Output is correct
26 Correct 119 ms 151800 KB Output is correct
27 Correct 119 ms 151800 KB Output is correct
28 Correct 119 ms 151032 KB Output is correct
29 Correct 120 ms 151288 KB Output is correct
30 Correct 119 ms 151516 KB Output is correct
31 Correct 120 ms 151288 KB Output is correct
32 Correct 123 ms 151416 KB Output is correct
33 Correct 228 ms 186488 KB Output is correct
34 Correct 229 ms 186616 KB Output is correct
35 Correct 227 ms 186488 KB Output is correct
36 Correct 225 ms 186488 KB Output is correct
37 Correct 345 ms 199800 KB Output is correct
38 Correct 350 ms 200312 KB Output is correct
39 Correct 350 ms 200440 KB Output is correct
40 Correct 329 ms 196984 KB Output is correct
41 Correct 284 ms 190712 KB Output is correct
42 Correct 304 ms 192248 KB Output is correct
43 Correct 361 ms 194952 KB Output is correct
44 Correct 350 ms 195448 KB Output is correct
45 Correct 220 ms 171552 KB Output is correct
46 Correct 221 ms 171384 KB Output is correct
47 Correct 341 ms 193552 KB Output is correct
48 Correct 342 ms 194296 KB Output is correct
49 Correct 104 ms 148128 KB Output is correct
50 Correct 107 ms 147960 KB Output is correct
51 Correct 105 ms 147960 KB Output is correct
52 Correct 104 ms 147324 KB Output is correct
53 Correct 105 ms 148088 KB Output is correct
54 Correct 104 ms 148012 KB Output is correct
55 Correct 105 ms 148088 KB Output is correct
56 Correct 104 ms 147960 KB Output is correct
57 Correct 104 ms 148088 KB Output is correct
58 Correct 100 ms 147704 KB Output is correct
59 Correct 105 ms 147832 KB Output is correct
60 Correct 100 ms 147324 KB Output is correct
61 Correct 1244 ms 398240 KB Output is correct
62 Correct 2554 ms 690676 KB Output is correct
63 Correct 2570 ms 693444 KB Output is correct
64 Correct 2618 ms 693284 KB Output is correct
65 Correct 927 ms 378872 KB Output is correct
66 Correct 1592 ms 585628 KB Output is correct
67 Correct 1703 ms 614552 KB Output is correct
68 Correct 1891 ms 624700 KB Output is correct
69 Correct 1850 ms 624632 KB Output is correct
70 Correct 1850 ms 624632 KB Output is correct
71 Correct 1856 ms 624668 KB Output is correct
72 Correct 3808 ms 810104 KB Output is correct
73 Correct 2229 ms 520744 KB Output is correct
74 Correct 2316 ms 530424 KB Output is correct
75 Correct 3673 ms 769884 KB Output is correct
76 Correct 2304 ms 514612 KB Output is correct
77 Correct 2950 ms 637800 KB Output is correct
78 Correct 3800 ms 766232 KB Output is correct
79 Correct 2089 ms 518900 KB Output is correct
80 Correct 3445 ms 754348 KB Output is correct
81 Correct 3361 ms 728468 KB Output is correct
82 Correct 2222 ms 552312 KB Output is correct
83 Correct 3754 ms 827896 KB Output is correct
84 Correct 3832 ms 829040 KB Output is correct
85 Correct 3779 ms 856724 KB Output is correct
86 Correct 103 ms 147324 KB Output is correct
87 Correct 101 ms 147192 KB Output is correct
88 Correct 101 ms 147320 KB Output is correct
89 Correct 99 ms 147192 KB Output is correct
90 Correct 99 ms 147192 KB Output is correct