oj.uz

Submission #1028802

# Submission time Handle Problem Language Result Execution time Memory
1028802 2024-07-20T08:54:18 Z onbert Rectangles (IOI19_rect) C++17
72 / 100
 2604 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct range {
    int r, mx;
};
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<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();
    vector<pair<int,int>> cur;
    vector<int> temp;
    set<int> s;
    for (int i=0;i<n;i++) {
        cur.clear();
        for (int j=0;j<m;j++) cur.push_back({a[i][j], j});
        sort(cur.rbegin(), cur.rend());
        s.clear(); s.insert(-1); s.insert(INF);
        temp.clear();
        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({r, -1});
                }
            }
            temp.push_back(id);
        }
    }

    for (int j=0;j<m;j++) {
        cur.clear();
        for (int i=0;i<n;i++) cur.push_back({a[i][j], i});
        sort(cur.rbegin(), cur.rend());
        s.clear(); s.insert(-1); s.insert(INF);
        temp.clear();
        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({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());
            int sz = pos[I][l][r].size();
            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;
            }
        }
    }
    for (int I=0;I<=1;I++) {
        for (int i=0;i<n;i++) for (int j=0;j<m;j++) {
            for (auto &[r, mx]:start[I][i][j]) {
                int x = j, y = i;
                if (I==1) x = i, y = j;
                mx = (*lower_bound(pos[I][x][r].begin(), pos[I][x][r].end(), make_pair(y, -INF))).second;
            }
        }
    }
    ll ans = 0;
    vector<int> LOG;
    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);
        sort(start[1][i][j].begin(), start[1][i][j].end(), cmp1);
        int pt = -1;
        LOG.clear();
        for (auto [r, mx]:start[0][i][j]) {
            while (pt+1 < start[1][i][j].size() && start[1][i][j][pt+1].mx >= r) {
                pt++;
                update(start[1][i][j][pt].r, 1);
                LOG.push_back(start[1][i][j][pt].r);
            }
            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:115:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             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 228 ms 589652 KB Output is correct
2 Correct 219 ms 589908 KB Output is correct
3 Correct 252 ms 589768 KB Output is correct
4 Correct 220 ms 589908 KB Output is correct
5 Correct 220 ms 589692 KB Output is correct
6 Correct 221 ms 589904 KB Output is correct
7 Correct 223 ms 589736 KB Output is correct
8 Correct 214 ms 589792 KB Output is correct
9 Correct 203 ms 590164 KB Output is correct
10 Correct 204 ms 589876 KB Output is correct
11 Correct 208 ms 589900 KB Output is correct
12 Correct 245 ms 589712 KB Output is correct
13 Correct 218 ms 589652 KB Output is correct
14 Correct 205 ms 589816 KB Output is correct
15 Correct 213 ms 589664 KB Output is correct
16 Correct 213 ms 589836 KB Output is correct
17 Correct 211 ms 589652 KB Output is correct
18 Correct 233 ms 589652 KB Output is correct
19 Correct 207 ms 589648 KB Output is correct
20 Correct 203 ms 589792 KB Output is correct
21 Correct 205 ms 589648 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 589652 KB Output is correct
2 Correct 219 ms 589908 KB Output is correct
3 Correct 252 ms 589768 KB Output is correct
4 Correct 220 ms 589908 KB Output is correct
5 Correct 220 ms 589692 KB Output is correct
6 Correct 221 ms 589904 KB Output is correct
7 Correct 223 ms 589736 KB Output is correct
8 Correct 214 ms 589792 KB Output is correct
9 Correct 203 ms 590164 KB Output is correct
10 Correct 204 ms 589876 KB Output is correct
11 Correct 208 ms 589900 KB Output is correct
12 Correct 245 ms 589712 KB Output is correct
13 Correct 218 ms 589652 KB Output is correct
14 Correct 205 ms 589816 KB Output is correct
15 Correct 213 ms 589664 KB Output is correct
16 Correct 213 ms 589836 KB Output is correct
17 Correct 211 ms 589652 KB Output is correct
18 Correct 233 ms 589652 KB Output is correct
19 Correct 207 ms 589648 KB Output is correct
20 Correct 203 ms 589792 KB Output is correct
21 Correct 205 ms 589648 KB Output is correct
22 Correct 209 ms 590328 KB Output is correct
23 Correct 218 ms 590404 KB Output is correct
24 Correct 205 ms 590432 KB Output is correct
25 Correct 209 ms 589904 KB Output is correct
26 Correct 215 ms 590308 KB Output is correct
27 Correct 233 ms 590164 KB Output is correct
28 Correct 227 ms 590160 KB Output is correct
29 Correct 224 ms 589908 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 589652 KB Output is correct
2 Correct 219 ms 589908 KB Output is correct
3 Correct 252 ms 589768 KB Output is correct
4 Correct 220 ms 589908 KB Output is correct
5 Correct 220 ms 589692 KB Output is correct
6 Correct 221 ms 589904 KB Output is correct
7 Correct 223 ms 589736 KB Output is correct
8 Correct 214 ms 589792 KB Output is correct
9 Correct 203 ms 590164 KB Output is correct
10 Correct 204 ms 589876 KB Output is correct
11 Correct 208 ms 589900 KB Output is correct
12 Correct 245 ms 589712 KB Output is correct
13 Correct 218 ms 589652 KB Output is correct
14 Correct 205 ms 589816 KB Output is correct
15 Correct 213 ms 589664 KB Output is correct
16 Correct 213 ms 589836 KB Output is correct
17 Correct 209 ms 590328 KB Output is correct
18 Correct 218 ms 590404 KB Output is correct
19 Correct 205 ms 590432 KB Output is correct
20 Correct 209 ms 589904 KB Output is correct
21 Correct 215 ms 590308 KB Output is correct
22 Correct 233 ms 590164 KB Output is correct
23 Correct 227 ms 590160 KB Output is correct
24 Correct 224 ms 589908 KB Output is correct
25 Correct 211 ms 589652 KB Output is correct
26 Correct 233 ms 589652 KB Output is correct
27 Correct 207 ms 589648 KB Output is correct
28 Correct 203 ms 589792 KB Output is correct
29 Correct 205 ms 589648 KB Output is correct
30 Correct 236 ms 593832 KB Output is correct
31 Correct 238 ms 593744 KB Output is correct
32 Correct 229 ms 593744 KB Output is correct
33 Correct 257 ms 591444 KB Output is correct
34 Correct 270 ms 592720 KB Output is correct
35 Correct 249 ms 592980 KB Output is correct
36 Correct 254 ms 592720 KB Output is correct
37 Correct 262 ms 592720 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 589652 KB Output is correct
2 Correct 219 ms 589908 KB Output is correct
3 Correct 252 ms 589768 KB Output is correct
4 Correct 220 ms 589908 KB Output is correct
5 Correct 220 ms 589692 KB Output is correct
6 Correct 221 ms 589904 KB Output is correct
7 Correct 223 ms 589736 KB Output is correct
8 Correct 214 ms 589792 KB Output is correct
9 Correct 203 ms 590164 KB Output is correct
10 Correct 204 ms 589876 KB Output is correct
11 Correct 208 ms 589900 KB Output is correct
12 Correct 245 ms 589712 KB Output is correct
13 Correct 218 ms 589652 KB Output is correct
14 Correct 205 ms 589816 KB Output is correct
15 Correct 213 ms 589664 KB Output is correct
16 Correct 213 ms 589836 KB Output is correct
17 Correct 209 ms 590328 KB Output is correct
18 Correct 218 ms 590404 KB Output is correct
19 Correct 205 ms 590432 KB Output is correct
20 Correct 209 ms 589904 KB Output is correct
21 Correct 215 ms 590308 KB Output is correct
22 Correct 233 ms 590164 KB Output is correct
23 Correct 227 ms 590160 KB Output is correct
24 Correct 224 ms 589908 KB Output is correct
25 Correct 236 ms 593832 KB Output is correct
26 Correct 238 ms 593744 KB Output is correct
27 Correct 229 ms 593744 KB Output is correct
28 Correct 257 ms 591444 KB Output is correct
29 Correct 270 ms 592720 KB Output is correct
30 Correct 249 ms 592980 KB Output is correct
31 Correct 254 ms 592720 KB Output is correct
32 Correct 262 ms 592720 KB Output is correct
33 Correct 211 ms 589652 KB Output is correct
34 Correct 233 ms 589652 KB Output is correct
35 Correct 207 ms 589648 KB Output is correct
36 Correct 203 ms 589792 KB Output is correct
37 Correct 205 ms 589648 KB Output is correct
38 Correct 402 ms 628012 KB Output is correct
39 Correct 423 ms 624212 KB Output is correct
40 Correct 397 ms 624212 KB Output is correct
41 Correct 396 ms 620368 KB Output is correct
42 Correct 455 ms 639056 KB Output is correct
43 Correct 443 ms 639052 KB Output is correct
44 Correct 465 ms 639560 KB Output is correct
45 Correct 474 ms 636752 KB Output is correct
46 Correct 415 ms 605280 KB Output is correct
47 Correct 492 ms 609620 KB Output is correct
48 Correct 761 ms 625116 KB Output is correct
49 Correct 688 ms 627284 KB Output is correct
50 Correct 440 ms 608608 KB Output is correct
51 Correct 489 ms 608620 KB Output is correct
52 Correct 651 ms 623956 KB Output is correct
53 Correct 661 ms 624912 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 590416 KB Output is correct
2 Correct 229 ms 590416 KB Output is correct
3 Correct 224 ms 589904 KB Output is correct
4 Correct 232 ms 589632 KB Output is correct
5 Correct 329 ms 590420 KB Output is correct
6 Correct 243 ms 590668 KB Output is correct
7 Correct 232 ms 590424 KB Output is correct
8 Correct 220 ms 590420 KB Output is correct
9 Correct 233 ms 590420 KB Output is correct
10 Correct 219 ms 590056 KB Output is correct
11 Correct 226 ms 590240 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 589652 KB Output is correct
2 Correct 233 ms 589652 KB Output is correct
3 Correct 207 ms 589648 KB Output is correct
4 Correct 203 ms 589792 KB Output is correct
5 Correct 205 ms 589648 KB Output is correct
6 Correct 219 ms 589648 KB Output is correct
7 Correct 1231 ms 681808 KB Output is correct
8 Correct 2561 ms 788736 KB Output is correct
9 Correct 2569 ms 789584 KB Output is correct
10 Correct 2604 ms 789632 KB Output is correct
11 Correct 396 ms 619996 KB Output is correct
12 Correct 570 ms 647672 KB Output is correct
13 Correct 583 ms 650996 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 589652 KB Output is correct
2 Correct 219 ms 589908 KB Output is correct
3 Correct 252 ms 589768 KB Output is correct
4 Correct 220 ms 589908 KB Output is correct
5 Correct 220 ms 589692 KB Output is correct
6 Correct 221 ms 589904 KB Output is correct
7 Correct 223 ms 589736 KB Output is correct
8 Correct 214 ms 589792 KB Output is correct
9 Correct 203 ms 590164 KB Output is correct
10 Correct 204 ms 589876 KB Output is correct
11 Correct 208 ms 589900 KB Output is correct
12 Correct 245 ms 589712 KB Output is correct
13 Correct 218 ms 589652 KB Output is correct
14 Correct 205 ms 589816 KB Output is correct
15 Correct 213 ms 589664 KB Output is correct
16 Correct 213 ms 589836 KB Output is correct
17 Correct 209 ms 590328 KB Output is correct
18 Correct 218 ms 590404 KB Output is correct
19 Correct 205 ms 590432 KB Output is correct
20 Correct 209 ms 589904 KB Output is correct
21 Correct 215 ms 590308 KB Output is correct
22 Correct 233 ms 590164 KB Output is correct
23 Correct 227 ms 590160 KB Output is correct
24 Correct 224 ms 589908 KB Output is correct
25 Correct 236 ms 593832 KB Output is correct
26 Correct 238 ms 593744 KB Output is correct
27 Correct 229 ms 593744 KB Output is correct
28 Correct 257 ms 591444 KB Output is correct
29 Correct 270 ms 592720 KB Output is correct
30 Correct 249 ms 592980 KB Output is correct
31 Correct 254 ms 592720 KB Output is correct
32 Correct 262 ms 592720 KB Output is correct
33 Correct 402 ms 628012 KB Output is correct
34 Correct 423 ms 624212 KB Output is correct
35 Correct 397 ms 624212 KB Output is correct
36 Correct 396 ms 620368 KB Output is correct
37 Correct 455 ms 639056 KB Output is correct
38 Correct 443 ms 639052 KB Output is correct
39 Correct 465 ms 639560 KB Output is correct
40 Correct 474 ms 636752 KB Output is correct
41 Correct 415 ms 605280 KB Output is correct
42 Correct 492 ms 609620 KB Output is correct
43 Correct 761 ms 625116 KB Output is correct
44 Correct 688 ms 627284 KB Output is correct
45 Correct 440 ms 608608 KB Output is correct
46 Correct 489 ms 608620 KB Output is correct
47 Correct 651 ms 623956 KB Output is correct
48 Correct 661 ms 624912 KB Output is correct
49 Correct 235 ms 590416 KB Output is correct
50 Correct 229 ms 590416 KB Output is correct
51 Correct 224 ms 589904 KB Output is correct
52 Correct 232 ms 589632 KB Output is correct
53 Correct 329 ms 590420 KB Output is correct
54 Correct 243 ms 590668 KB Output is correct
55 Correct 232 ms 590424 KB Output is correct
56 Correct 220 ms 590420 KB Output is correct
57 Correct 233 ms 590420 KB Output is correct
58 Correct 219 ms 590056 KB Output is correct
59 Correct 226 ms 590240 KB Output is correct
60 Correct 219 ms 589648 KB Output is correct
61 Correct 1231 ms 681808 KB Output is correct
62 Correct 2561 ms 788736 KB Output is correct
63 Correct 2569 ms 789584 KB Output is correct
64 Correct 2604 ms 789632 KB Output is correct
65 Correct 396 ms 619996 KB Output is correct
66 Correct 570 ms 647672 KB Output is correct
67 Correct 583 ms 650996 KB Output is correct
68 Correct 211 ms 589652 KB Output is correct
69 Correct 233 ms 589652 KB Output is correct
70 Correct 207 ms 589648 KB Output is correct
71 Correct 203 ms 589792 KB Output is correct
72 Correct 205 ms 589648 KB Output is correct
73 Runtime error 2319 ms 1048576 KB Execution killed with signal 9
74 Halted 0 ms 0 KB -