oj.uz

Submission #1028778

# Submission time Handle Problem Language Result Execution time Memory
1028778 2024-07-20T08:34:10 Z onbert Rectangles (IOI19_rect) C++17
72 / 100
 3041 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct range {
    int l, r, mx;
    // bool operator == (const range &b) const {
    //     return (l==b.l && r==b.r);
    // }
};
bool cmp0(range a, range b) {return a.r > b.r;}
bool cmp1(range a, range b) {return a.mx > b.mx;}
const int maxn = 2505, INF = 1e9;
int n, m;
vector<vector<int>> a;
vector<pair<int,int>> pos[2][maxn][maxn];
vector<range> start[2][maxn][maxn];

int fen[maxn];
void update(int id, int val) {
    while (id<maxn) {
        fen[id] += val;
        id += (id & -id);
    }
}
int qry(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

long long count_rectangles(vector<vector<int32_t>> A) {
	n = A.size(), m = A[0].size();
    a.resize(n);
    for (int i=0;i<n;i++) {
        a[i].resize(m);
        for (int j=0;j<m;j++) a[i][j] = A[i][j];
    }
    for (int i=0;i<n;i++) {
        vector<pair<int,int>> cur;
        for (int j=0;j<m;j++) cur.push_back({a[i][j], j});
        sort(cur.rbegin(), cur.rend());
        set<int> s; s.insert(-1); s.insert(INF);
        vector<int> temp;
        for (int j=0;j<m;j++) {
            auto [val, id] = cur[j];
            if (j>0 && val!=cur[j-1].first) {
                for (int x:temp) s.insert(x);
                temp.clear();
            }
            auto it = s.upper_bound(id);
            int l = *prev(it), r = *it;
            if (l!=-1 && r!=INF) {
                l++, r--;
                if (pos[0][l][r].size()==0 || pos[0][l][r].back().first!=i) {
                    pos[0][l][r].push_back({i, -1});
                    start[0][i][l].push_back({l, r, -1});
                }
            }
            temp.push_back(id);
        }
    }

    for (int j=0;j<m;j++) {
        vector<pair<int,int>> cur;
        for (int i=0;i<n;i++) cur.push_back({a[i][j], i});
        sort(cur.rbegin(), cur.rend());
        set<int> s; s.insert(-1); s.insert(INF);
        vector<int> temp;
        for (int i=0;i<n;i++) {
            auto [val, id] = cur[i];
            if (i>0 && val!=cur[i-1].first) {
                for (int x:temp) s.insert(x);
                temp.clear();
            }
            auto it = s.upper_bound(id);
            int l = *prev(it), r = *it;
            if (l!=-1 && r!=INF) {
                l++, r--;
                if (pos[1][l][r].size()==0 || pos[1][l][r].back().first!=j) {
                    pos[1][l][r].push_back({j, -1});
                    start[1][l][j].push_back({l, r, -1});
                }
            }
            temp.push_back(id);
        }
    }

    for (int I=0;I<=1;I++) {
        int nn = m;
        if (I==1) nn = n;
        for (int l=0;l<nn;l++) for (int r=l;r<nn;r++) {
            sort(pos[I][l][r].begin(), pos[I][l][r].end());
            // pos[I][l][r].erase(unique(pos[I][l][r].begin(), pos[I][l][r].end()), pos[I][l][r].end());
            int sz = pos[I][l][r].size();
            // if (I==1 && sz>0) cout << l << " " << r << " " << sz << endl;
            for (int i=sz-1;i>=0;i--) {
                if (i==sz-1 || pos[I][l][r][i+1].first!=pos[I][l][r][i].first+1) pos[I][l][r][i].second = pos[I][l][r][i].first;
                else pos[I][l][r][i].second = pos[I][l][r][i+1].second;
                // if (I==1) cout << pos[I][l][r][i].first << " " << pos[I][l][r][i].second << endl;
            }
        }
    }
    for (int I=0;I<=1;I++) {
        for (int i=0;i<n;i++) for (int j=0;j<m;j++) {
            // cout << "test " << I << " " << i << " " << j << endl;
            for (auto &[l, r, mx]:start[I][i][j]) {
                // cout << l << " " << r << " " << mx << endl;
                int id = i;
                if (I==1) id = j;
                mx = (*lower_bound(pos[I][l][r].begin(), pos[I][l][r].end(), make_pair(id, -INF))).second;
            }
        }
    }
    int ans = 0;
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) {
        sort(start[0][i][j].begin(), start[0][i][j].end(), cmp0);
        // start[0][i][j].erase(unique(start[0][i][j].begin(), start[0][i][j].end()), start[0][i][j].end());
        sort(start[1][i][j].begin(), start[1][i][j].end(), cmp1);
        // start[1][i][j].erase(unique(start[1][i][j].begin(), start[1][i][j].end()), start[1][i][j].end());
        int pt = -1;
        vector<int> LOG;
        for (auto [l, r, mx]:start[0][i][j]) {
            while (pt+1 < start[1][i][j].size() && start[1][i][j][pt+1].mx >= r) {
                pt++;
                // if (i==1 && j==2) cout << start[1][i][j][pt].l << " " << start[1][i][j][pt].r << endl;
                update(start[1][i][j][pt].r, 1);
                LOG.push_back(start[1][i][j][pt].r);
            }
            // if (qry(mx) > 0) {
            //     cout << "ANS " << qry(mx) << endl;
            //     cout << i << " " << j << endl;
            //     cout << l << " " << r << endl;
            // }
            ans += qry(mx);
        }
        for (int x:LOG) update(x, -1);
    }
    return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:127:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             while (pt+1 < start[1][i][j].size() && start[1][i][j][pt+1].mx >= r) {
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 589652 KB Output is correct
2 Correct 247 ms 589784 KB Output is correct
3 Correct 269 ms 589912 KB Output is correct
4 Correct 278 ms 589844 KB Output is correct
5 Correct 221 ms 589648 KB Output is correct
6 Correct 221 ms 589924 KB Output is correct
7 Correct 233 ms 589904 KB Output is correct
8 Correct 255 ms 590032 KB Output is correct
9 Correct 216 ms 589872 KB Output is correct
10 Correct 284 ms 589780 KB Output is correct
11 Correct 236 ms 589904 KB Output is correct
12 Correct 215 ms 589904 KB Output is correct
13 Correct 257 ms 589648 KB Output is correct
14 Correct 212 ms 589836 KB Output is correct
15 Correct 224 ms 589652 KB Output is correct
16 Correct 214 ms 589652 KB Output is correct
17 Correct 223 ms 589652 KB Output is correct
18 Correct 245 ms 589816 KB Output is correct
19 Correct 220 ms 589652 KB Output is correct
20 Correct 219 ms 589652 KB Output is correct
21 Correct 221 ms 589652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 589652 KB Output is correct
2 Correct 247 ms 589784 KB Output is correct
3 Correct 269 ms 589912 KB Output is correct
4 Correct 278 ms 589844 KB Output is correct
5 Correct 221 ms 589648 KB Output is correct
6 Correct 221 ms 589924 KB Output is correct
7 Correct 233 ms 589904 KB Output is correct
8 Correct 255 ms 590032 KB Output is correct
9 Correct 216 ms 589872 KB Output is correct
10 Correct 284 ms 589780 KB Output is correct
11 Correct 236 ms 589904 KB Output is correct
12 Correct 215 ms 589904 KB Output is correct
13 Correct 257 ms 589648 KB Output is correct
14 Correct 212 ms 589836 KB Output is correct
15 Correct 224 ms 589652 KB Output is correct
16 Correct 214 ms 589652 KB Output is correct
17 Correct 223 ms 589652 KB Output is correct
18 Correct 245 ms 589816 KB Output is correct
19 Correct 220 ms 589652 KB Output is correct
20 Correct 219 ms 589652 KB Output is correct
21 Correct 221 ms 589652 KB Output is correct
22 Correct 224 ms 590672 KB Output is correct
23 Correct 238 ms 590568 KB Output is correct
24 Correct 233 ms 590928 KB Output is correct
25 Correct 229 ms 590164 KB Output is correct
26 Correct 231 ms 590420 KB Output is correct
27 Correct 226 ms 590536 KB Output is correct
28 Correct 221 ms 590416 KB Output is correct
29 Correct 235 ms 590044 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 589652 KB Output is correct
2 Correct 247 ms 589784 KB Output is correct
3 Correct 269 ms 589912 KB Output is correct
4 Correct 278 ms 589844 KB Output is correct
5 Correct 221 ms 589648 KB Output is correct
6 Correct 221 ms 589924 KB Output is correct
7 Correct 233 ms 589904 KB Output is correct
8 Correct 255 ms 590032 KB Output is correct
9 Correct 216 ms 589872 KB Output is correct
10 Correct 284 ms 589780 KB Output is correct
11 Correct 236 ms 589904 KB Output is correct
12 Correct 215 ms 589904 KB Output is correct
13 Correct 257 ms 589648 KB Output is correct
14 Correct 212 ms 589836 KB Output is correct
15 Correct 224 ms 589652 KB Output is correct
16 Correct 214 ms 589652 KB Output is correct
17 Correct 224 ms 590672 KB Output is correct
18 Correct 238 ms 590568 KB Output is correct
19 Correct 233 ms 590928 KB Output is correct
20 Correct 229 ms 590164 KB Output is correct
21 Correct 231 ms 590420 KB Output is correct
22 Correct 226 ms 590536 KB Output is correct
23 Correct 221 ms 590416 KB Output is correct
24 Correct 235 ms 590044 KB Output is correct
25 Correct 223 ms 589652 KB Output is correct
26 Correct 245 ms 589816 KB Output is correct
27 Correct 220 ms 589652 KB Output is correct
28 Correct 219 ms 589652 KB Output is correct
29 Correct 221 ms 589652 KB Output is correct
30 Correct 249 ms 595112 KB Output is correct
31 Correct 266 ms 595116 KB Output is correct
32 Correct 275 ms 595028 KB Output is correct
33 Correct 269 ms 592224 KB Output is correct
34 Correct 258 ms 594988 KB Output is correct
35 Correct 275 ms 594796 KB Output is correct
36 Correct 260 ms 594516 KB Output is correct
37 Correct 260 ms 594256 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 589652 KB Output is correct
2 Correct 247 ms 589784 KB Output is correct
3 Correct 269 ms 589912 KB Output is correct
4 Correct 278 ms 589844 KB Output is correct
5 Correct 221 ms 589648 KB Output is correct
6 Correct 221 ms 589924 KB Output is correct
7 Correct 233 ms 589904 KB Output is correct
8 Correct 255 ms 590032 KB Output is correct
9 Correct 216 ms 589872 KB Output is correct
10 Correct 284 ms 589780 KB Output is correct
11 Correct 236 ms 589904 KB Output is correct
12 Correct 215 ms 589904 KB Output is correct
13 Correct 257 ms 589648 KB Output is correct
14 Correct 212 ms 589836 KB Output is correct
15 Correct 224 ms 589652 KB Output is correct
16 Correct 214 ms 589652 KB Output is correct
17 Correct 224 ms 590672 KB Output is correct
18 Correct 238 ms 590568 KB Output is correct
19 Correct 233 ms 590928 KB Output is correct
20 Correct 229 ms 590164 KB Output is correct
21 Correct 231 ms 590420 KB Output is correct
22 Correct 226 ms 590536 KB Output is correct
23 Correct 221 ms 590416 KB Output is correct
24 Correct 235 ms 590044 KB Output is correct
25 Correct 249 ms 595112 KB Output is correct
26 Correct 266 ms 595116 KB Output is correct
27 Correct 275 ms 595028 KB Output is correct
28 Correct 269 ms 592224 KB Output is correct
29 Correct 258 ms 594988 KB Output is correct
30 Correct 275 ms 594796 KB Output is correct
31 Correct 260 ms 594516 KB Output is correct
32 Correct 260 ms 594256 KB Output is correct
33 Correct 223 ms 589652 KB Output is correct
34 Correct 245 ms 589816 KB Output is correct
35 Correct 220 ms 589652 KB Output is correct
36 Correct 219 ms 589652 KB Output is correct
37 Correct 221 ms 589652 KB Output is correct
38 Correct 541 ms 632656 KB Output is correct
39 Correct 450 ms 631632 KB Output is correct
40 Correct 484 ms 631632 KB Output is correct
41 Correct 430 ms 630608 KB Output is correct
42 Correct 523 ms 657384 KB Output is correct
43 Correct 524 ms 656980 KB Output is correct
44 Correct 514 ms 657756 KB Output is correct
45 Correct 471 ms 653148 KB Output is correct
46 Correct 381 ms 610968 KB Output is correct
47 Correct 434 ms 618416 KB Output is correct
48 Correct 737 ms 649048 KB Output is correct
49 Correct 745 ms 650032 KB Output is correct
50 Correct 466 ms 619856 KB Output is correct
51 Correct 458 ms 619860 KB Output is correct
52 Correct 687 ms 645972 KB Output is correct
53 Correct 694 ms 649812 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 590484 KB Output is correct
2 Correct 225 ms 590420 KB Output is correct
3 Correct 226 ms 589900 KB Output is correct
4 Correct 226 ms 589920 KB Output is correct
5 Correct 233 ms 590416 KB Output is correct
6 Correct 234 ms 590496 KB Output is correct
7 Correct 229 ms 590556 KB Output is correct
8 Correct 219 ms 590352 KB Output is correct
9 Correct 226 ms 590560 KB Output is correct
10 Correct 231 ms 590028 KB Output is correct
11 Correct 233 ms 590164 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 589652 KB Output is correct
2 Correct 245 ms 589816 KB Output is correct
3 Correct 220 ms 589652 KB Output is correct
4 Correct 219 ms 589652 KB Output is correct
5 Correct 221 ms 589652 KB Output is correct
6 Correct 234 ms 589752 KB Output is correct
7 Correct 1454 ms 717140 KB Output is correct
8 Correct 3041 ms 867376 KB Output is correct
9 Correct 2982 ms 870768 KB Output is correct
10 Correct 2923 ms 870828 KB Output is correct
11 Correct 412 ms 638288 KB Output is correct
12 Correct 619 ms 681800 KB Output is correct
13 Correct 652 ms 687956 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 589652 KB Output is correct
2 Correct 247 ms 589784 KB Output is correct
3 Correct 269 ms 589912 KB Output is correct
4 Correct 278 ms 589844 KB Output is correct
5 Correct 221 ms 589648 KB Output is correct
6 Correct 221 ms 589924 KB Output is correct
7 Correct 233 ms 589904 KB Output is correct
8 Correct 255 ms 590032 KB Output is correct
9 Correct 216 ms 589872 KB Output is correct
10 Correct 284 ms 589780 KB Output is correct
11 Correct 236 ms 589904 KB Output is correct
12 Correct 215 ms 589904 KB Output is correct
13 Correct 257 ms 589648 KB Output is correct
14 Correct 212 ms 589836 KB Output is correct
15 Correct 224 ms 589652 KB Output is correct
16 Correct 214 ms 589652 KB Output is correct
17 Correct 224 ms 590672 KB Output is correct
18 Correct 238 ms 590568 KB Output is correct
19 Correct 233 ms 590928 KB Output is correct
20 Correct 229 ms 590164 KB Output is correct
21 Correct 231 ms 590420 KB Output is correct
22 Correct 226 ms 590536 KB Output is correct
23 Correct 221 ms 590416 KB Output is correct
24 Correct 235 ms 590044 KB Output is correct
25 Correct 249 ms 595112 KB Output is correct
26 Correct 266 ms 595116 KB Output is correct
27 Correct 275 ms 595028 KB Output is correct
28 Correct 269 ms 592224 KB Output is correct
29 Correct 258 ms 594988 KB Output is correct
30 Correct 275 ms 594796 KB Output is correct
31 Correct 260 ms 594516 KB Output is correct
32 Correct 260 ms 594256 KB Output is correct
33 Correct 541 ms 632656 KB Output is correct
34 Correct 450 ms 631632 KB Output is correct
35 Correct 484 ms 631632 KB Output is correct
36 Correct 430 ms 630608 KB Output is correct
37 Correct 523 ms 657384 KB Output is correct
38 Correct 524 ms 656980 KB Output is correct
39 Correct 514 ms 657756 KB Output is correct
40 Correct 471 ms 653148 KB Output is correct
41 Correct 381 ms 610968 KB Output is correct
42 Correct 434 ms 618416 KB Output is correct
43 Correct 737 ms 649048 KB Output is correct
44 Correct 745 ms 650032 KB Output is correct
45 Correct 466 ms 619856 KB Output is correct
46 Correct 458 ms 619860 KB Output is correct
47 Correct 687 ms 645972 KB Output is correct
48 Correct 694 ms 649812 KB Output is correct
49 Correct 258 ms 590484 KB Output is correct
50 Correct 225 ms 590420 KB Output is correct
51 Correct 226 ms 589900 KB Output is correct
52 Correct 226 ms 589920 KB Output is correct
53 Correct 233 ms 590416 KB Output is correct
54 Correct 234 ms 590496 KB Output is correct
55 Correct 229 ms 590556 KB Output is correct
56 Correct 219 ms 590352 KB Output is correct
57 Correct 226 ms 590560 KB Output is correct
58 Correct 231 ms 590028 KB Output is correct
59 Correct 233 ms 590164 KB Output is correct
60 Correct 234 ms 589752 KB Output is correct
61 Correct 1454 ms 717140 KB Output is correct
62 Correct 3041 ms 867376 KB Output is correct
63 Correct 2982 ms 870768 KB Output is correct
64 Correct 2923 ms 870828 KB Output is correct
65 Correct 412 ms 638288 KB Output is correct
66 Correct 619 ms 681800 KB Output is correct
67 Correct 652 ms 687956 KB Output is correct
68 Correct 223 ms 589652 KB Output is correct
69 Correct 245 ms 589816 KB Output is correct
70 Correct 220 ms 589652 KB Output is correct
71 Correct 219 ms 589652 KB Output is correct
72 Correct 221 ms 589652 KB Output is correct
73 Runtime error 2103 ms 1048576 KB Execution killed with signal 9
74 Halted 0 ms 0 KB -