oj.uz

Submission #987251

# Submission time Handle Problem Language Result Execution time Memory
987251 2024-05-22T12:44:08 Z AdamGS Rectangles (IOI19_rect) C++17
100 / 100
 2058 ms 625332 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2507;
int tr[4*LIM], N=1;
vector<pair<int,int>>lewo[LIM][LIM], gora[LIM][LIM];
void upd(int v) {
  v+=N;
  while(v) {
    ++tr[v];
    v/=2;
  }
}
void upd2(int v) {
  v+=N;
  while(v) {
    --tr[v];
    v/=2;
  }
}
int cnt(int v) {
  v+=N;
  int ans=tr[v];
  while(v) {
    if(v&1) ans+=tr[v-1];
    v/=2;
  }
  return ans;
}
ll count_rectangles(vector<vector<int>>A) {
  int n=A.size(), m=A[0].size();
  while(N<max(n, m)) N*=2;
  rep(i, n) {
    vector<int>P;
    rep(j, m) {
      int lst=-1;
      while(P.size()>0 && A[i][P.back()]<A[i][j]) {
        lst=A[i][P.back()];
        P.pop_back();
        if(P.size() && A[i][P.back()]!=lst) lewo[i][j].pb({j-P.back()-1, 1});
      }
      P.pb(j);
      if(!i) continue;
      int l=0;
      rep(a, lewo[i][j].size()) {
        while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
        if(l<lewo[i-1][j].size() && lewo[i-1][j][l].st==lewo[i][j][a].st) lewo[i][j][a].nd+=lewo[i-1][j][l].nd;
      }
    }
  }
  rep(j, m) {
    vector<int>P;
    rep(i, n) {
      int lst=-1;
      while(P.size()>0 && A[P.back()][j]<A[i][j]) {
        lst=A[P.back()][j];
        P.pop_back();
        if(P.size() && lst!=A[P.back()][j]) gora[i][j].pb({i-P.back()-1, 1});
      }
      P.pb(i);
      if(!j) continue;
      int l=0;
      rep(a, gora[i][j].size()) {
        while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
        if(l<gora[i][j-1].size() && gora[i][j-1][l].st==gora[i][j][a].st) gora[i][j][a].nd+=gora[i][j-1][l].nd;
      }
    }
  }
  ll ans=0;
  rep(i, n) rep(j, m) {
    rep(l, lewo[i][j].size()) swap(lewo[i][j][l].st, lewo[i][j][l].nd);
    sort(all(lewo[i][j]));
  }
  rep(i, n-1) rep(j, m-1) {
    int b=(int)lewo[i][j+1].size()-1;
    for(int a=(int)gora[i+1][j].size()-1; a>=0; --a) {
      while(b>=0 && lewo[i][j+1][b].st>=gora[i+1][j][a].st) {
        upd(lewo[i][j+1][b].nd);
        --b;
      }
      ans+=(ll)cnt(gora[i+1][j][a].nd);
    }
    ++b;
    while(b<lewo[i][j+1].size()) {
      upd2(lewo[i][j+1][b].nd);
      ++b;
    }
  }
  return ans;
}

Compilation message

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
rect.cpp:51:7: note: in expansion of macro 'rep'
   51 |       rep(a, lewo[i][j].size()) {
      |       ^~~
rect.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:53:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if(l<lewo[i-1][j].size() && lewo[i-1][j][l].st==lewo[i][j][a].st) lewo[i][j][a].nd+=lewo[i-1][j][l].nd;
      |            ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
rect.cpp:69:7: note: in expansion of macro 'rep'
   69 |       rep(a, gora[i][j].size()) {
      |       ^~~
rect.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:71:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if(l<gora[i][j-1].size() && gora[i][j-1][l].st==gora[i][j][a].st) gora[i][j][a].nd+=gora[i][j-1][l].nd;
      |            ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
rect.cpp:77:5: note: in expansion of macro 'rep'
   77 |     rep(l, lewo[i][j].size()) swap(lewo[i][j][l].st, lewo[i][j][l].nd);
      |     ^~~
rect.cpp:90:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     while(b<lewo[i][j+1].size()) {
      |           ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 295504 KB Output is correct
2 Correct 161 ms 295624 KB Output is correct
3 Correct 169 ms 295504 KB Output is correct
4 Correct 142 ms 295504 KB Output is correct
5 Correct 145 ms 295604 KB Output is correct
6 Correct 141 ms 295408 KB Output is correct
7 Correct 157 ms 295556 KB Output is correct
8 Correct 160 ms 295504 KB Output is correct
9 Correct 157 ms 295508 KB Output is correct
10 Correct 136 ms 295596 KB Output is correct
11 Correct 159 ms 295472 KB Output is correct
12 Correct 156 ms 295504 KB Output is correct
13 Correct 162 ms 295420 KB Output is correct
14 Correct 162 ms 295504 KB Output is correct
15 Correct 165 ms 295532 KB Output is correct
16 Correct 158 ms 295520 KB Output is correct
17 Correct 158 ms 295508 KB Output is correct
18 Correct 143 ms 295508 KB Output is correct
19 Correct 169 ms 295504 KB Output is correct
20 Correct 157 ms 295500 KB Output is correct
21 Correct 138 ms 295424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 295504 KB Output is correct
2 Correct 161 ms 295624 KB Output is correct
3 Correct 169 ms 295504 KB Output is correct
4 Correct 142 ms 295504 KB Output is correct
5 Correct 145 ms 295604 KB Output is correct
6 Correct 141 ms 295408 KB Output is correct
7 Correct 157 ms 295556 KB Output is correct
8 Correct 160 ms 295504 KB Output is correct
9 Correct 157 ms 295508 KB Output is correct
10 Correct 136 ms 295596 KB Output is correct
11 Correct 159 ms 295472 KB Output is correct
12 Correct 156 ms 295504 KB Output is correct
13 Correct 162 ms 295420 KB Output is correct
14 Correct 162 ms 295504 KB Output is correct
15 Correct 165 ms 295532 KB Output is correct
16 Correct 158 ms 295520 KB Output is correct
17 Correct 158 ms 295508 KB Output is correct
18 Correct 143 ms 295508 KB Output is correct
19 Correct 169 ms 295504 KB Output is correct
20 Correct 157 ms 295500 KB Output is correct
21 Correct 138 ms 295424 KB Output is correct
22 Correct 143 ms 295764 KB Output is correct
23 Correct 163 ms 295708 KB Output is correct
24 Correct 167 ms 295764 KB Output is correct
25 Correct 160 ms 295552 KB Output is correct
26 Correct 155 ms 295764 KB Output is correct
27 Correct 137 ms 295756 KB Output is correct
28 Correct 161 ms 295760 KB Output is correct
29 Correct 160 ms 295504 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 295504 KB Output is correct
2 Correct 161 ms 295624 KB Output is correct
3 Correct 169 ms 295504 KB Output is correct
4 Correct 142 ms 295504 KB Output is correct
5 Correct 145 ms 295604 KB Output is correct
6 Correct 141 ms 295408 KB Output is correct
7 Correct 157 ms 295556 KB Output is correct
8 Correct 160 ms 295504 KB Output is correct
9 Correct 157 ms 295508 KB Output is correct
10 Correct 136 ms 295596 KB Output is correct
11 Correct 159 ms 295472 KB Output is correct
12 Correct 156 ms 295504 KB Output is correct
13 Correct 162 ms 295420 KB Output is correct
14 Correct 162 ms 295504 KB Output is correct
15 Correct 165 ms 295532 KB Output is correct
16 Correct 158 ms 295520 KB Output is correct
17 Correct 143 ms 295764 KB Output is correct
18 Correct 163 ms 295708 KB Output is correct
19 Correct 167 ms 295764 KB Output is correct
20 Correct 160 ms 295552 KB Output is correct
21 Correct 155 ms 295764 KB Output is correct
22 Correct 137 ms 295756 KB Output is correct
23 Correct 161 ms 295760 KB Output is correct
24 Correct 160 ms 295504 KB Output is correct
25 Correct 158 ms 295508 KB Output is correct
26 Correct 143 ms 295508 KB Output is correct
27 Correct 169 ms 295504 KB Output is correct
28 Correct 157 ms 295500 KB Output is correct
29 Correct 138 ms 295424 KB Output is correct
30 Correct 165 ms 296748 KB Output is correct
31 Correct 166 ms 296844 KB Output is correct
32 Correct 164 ms 296864 KB Output is correct
33 Correct 144 ms 296620 KB Output is correct
34 Correct 172 ms 297324 KB Output is correct
35 Correct 166 ms 297580 KB Output is correct
36 Correct 167 ms 297348 KB Output is correct
37 Correct 150 ms 297552 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 295504 KB Output is correct
2 Correct 161 ms 295624 KB Output is correct
3 Correct 169 ms 295504 KB Output is correct
4 Correct 142 ms 295504 KB Output is correct
5 Correct 145 ms 295604 KB Output is correct
6 Correct 141 ms 295408 KB Output is correct
7 Correct 157 ms 295556 KB Output is correct
8 Correct 160 ms 295504 KB Output is correct
9 Correct 157 ms 295508 KB Output is correct
10 Correct 136 ms 295596 KB Output is correct
11 Correct 159 ms 295472 KB Output is correct
12 Correct 156 ms 295504 KB Output is correct
13 Correct 162 ms 295420 KB Output is correct
14 Correct 162 ms 295504 KB Output is correct
15 Correct 165 ms 295532 KB Output is correct
16 Correct 158 ms 295520 KB Output is correct
17 Correct 143 ms 295764 KB Output is correct
18 Correct 163 ms 295708 KB Output is correct
19 Correct 167 ms 295764 KB Output is correct
20 Correct 160 ms 295552 KB Output is correct
21 Correct 155 ms 295764 KB Output is correct
22 Correct 137 ms 295756 KB Output is correct
23 Correct 161 ms 295760 KB Output is correct
24 Correct 160 ms 295504 KB Output is correct
25 Correct 165 ms 296748 KB Output is correct
26 Correct 166 ms 296844 KB Output is correct
27 Correct 164 ms 296864 KB Output is correct
28 Correct 144 ms 296620 KB Output is correct
29 Correct 172 ms 297324 KB Output is correct
30 Correct 166 ms 297580 KB Output is correct
31 Correct 167 ms 297348 KB Output is correct
32 Correct 150 ms 297552 KB Output is correct
33 Correct 158 ms 295508 KB Output is correct
34 Correct 143 ms 295508 KB Output is correct
35 Correct 169 ms 295504 KB Output is correct
36 Correct 157 ms 295500 KB Output is correct
37 Correct 138 ms 295424 KB Output is correct
38 Correct 214 ms 308304 KB Output is correct
39 Correct 207 ms 312912 KB Output is correct
40 Correct 225 ms 313092 KB Output is correct
41 Correct 224 ms 317780 KB Output is correct
42 Correct 225 ms 313784 KB Output is correct
43 Correct 226 ms 314016 KB Output is correct
44 Correct 239 ms 314192 KB Output is correct
45 Correct 201 ms 313428 KB Output is correct
46 Correct 210 ms 308228 KB Output is correct
47 Correct 220 ms 310584 KB Output is correct
48 Correct 278 ms 319224 KB Output is correct
49 Correct 285 ms 321148 KB Output is correct
50 Correct 219 ms 308372 KB Output is correct
51 Correct 207 ms 308304 KB Output is correct
52 Correct 275 ms 318808 KB Output is correct
53 Correct 259 ms 319828 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 295656 KB Output is correct
2 Correct 165 ms 295672 KB Output is correct
3 Correct 149 ms 295680 KB Output is correct
4 Correct 136 ms 295508 KB Output is correct
5 Correct 162 ms 295764 KB Output is correct
6 Correct 142 ms 295876 KB Output is correct
7 Correct 164 ms 295708 KB Output is correct
8 Correct 161 ms 295728 KB Output is correct
9 Correct 160 ms 295684 KB Output is correct
10 Correct 161 ms 295628 KB Output is correct
11 Correct 161 ms 295768 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 295508 KB Output is correct
2 Correct 143 ms 295508 KB Output is correct
3 Correct 169 ms 295504 KB Output is correct
4 Correct 157 ms 295500 KB Output is correct
5 Correct 138 ms 295424 KB Output is correct
6 Correct 160 ms 295508 KB Output is correct
7 Correct 435 ms 368464 KB Output is correct
8 Correct 901 ms 454052 KB Output is correct
9 Correct 908 ms 454744 KB Output is correct
10 Correct 830 ms 455020 KB Output is correct
11 Correct 292 ms 326108 KB Output is correct
12 Correct 482 ms 352900 KB Output is correct
13 Correct 416 ms 356820 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 295504 KB Output is correct
2 Correct 161 ms 295624 KB Output is correct
3 Correct 169 ms 295504 KB Output is correct
4 Correct 142 ms 295504 KB Output is correct
5 Correct 145 ms 295604 KB Output is correct
6 Correct 141 ms 295408 KB Output is correct
7 Correct 157 ms 295556 KB Output is correct
8 Correct 160 ms 295504 KB Output is correct
9 Correct 157 ms 295508 KB Output is correct
10 Correct 136 ms 295596 KB Output is correct
11 Correct 159 ms 295472 KB Output is correct
12 Correct 156 ms 295504 KB Output is correct
13 Correct 162 ms 295420 KB Output is correct
14 Correct 162 ms 295504 KB Output is correct
15 Correct 165 ms 295532 KB Output is correct
16 Correct 158 ms 295520 KB Output is correct
17 Correct 143 ms 295764 KB Output is correct
18 Correct 163 ms 295708 KB Output is correct
19 Correct 167 ms 295764 KB Output is correct
20 Correct 160 ms 295552 KB Output is correct
21 Correct 155 ms 295764 KB Output is correct
22 Correct 137 ms 295756 KB Output is correct
23 Correct 161 ms 295760 KB Output is correct
24 Correct 160 ms 295504 KB Output is correct
25 Correct 165 ms 296748 KB Output is correct
26 Correct 166 ms 296844 KB Output is correct
27 Correct 164 ms 296864 KB Output is correct
28 Correct 144 ms 296620 KB Output is correct
29 Correct 172 ms 297324 KB Output is correct
30 Correct 166 ms 297580 KB Output is correct
31 Correct 167 ms 297348 KB Output is correct
32 Correct 150 ms 297552 KB Output is correct
33 Correct 214 ms 308304 KB Output is correct
34 Correct 207 ms 312912 KB Output is correct
35 Correct 225 ms 313092 KB Output is correct
36 Correct 224 ms 317780 KB Output is correct
37 Correct 225 ms 313784 KB Output is correct
38 Correct 226 ms 314016 KB Output is correct
39 Correct 239 ms 314192 KB Output is correct
40 Correct 201 ms 313428 KB Output is correct
41 Correct 210 ms 308228 KB Output is correct
42 Correct 220 ms 310584 KB Output is correct
43 Correct 278 ms 319224 KB Output is correct
44 Correct 285 ms 321148 KB Output is correct
45 Correct 219 ms 308372 KB Output is correct
46 Correct 207 ms 308304 KB Output is correct
47 Correct 275 ms 318808 KB Output is correct
48 Correct 259 ms 319828 KB Output is correct
49 Correct 166 ms 295656 KB Output is correct
50 Correct 165 ms 295672 KB Output is correct
51 Correct 149 ms 295680 KB Output is correct
52 Correct 136 ms 295508 KB Output is correct
53 Correct 162 ms 295764 KB Output is correct
54 Correct 142 ms 295876 KB Output is correct
55 Correct 164 ms 295708 KB Output is correct
56 Correct 161 ms 295728 KB Output is correct
57 Correct 160 ms 295684 KB Output is correct
58 Correct 161 ms 295628 KB Output is correct
59 Correct 161 ms 295768 KB Output is correct
60 Correct 160 ms 295508 KB Output is correct
61 Correct 435 ms 368464 KB Output is correct
62 Correct 901 ms 454052 KB Output is correct
63 Correct 908 ms 454744 KB Output is correct
64 Correct 830 ms 455020 KB Output is correct
65 Correct 292 ms 326108 KB Output is correct
66 Correct 482 ms 352900 KB Output is correct
67 Correct 416 ms 356820 KB Output is correct
68 Correct 158 ms 295508 KB Output is correct
69 Correct 143 ms 295508 KB Output is correct
70 Correct 169 ms 295504 KB Output is correct
71 Correct 157 ms 295500 KB Output is correct
72 Correct 138 ms 295424 KB Output is correct
73 Correct 819 ms 452756 KB Output is correct
74 Correct 801 ms 519892 KB Output is correct
75 Correct 1332 ms 519700 KB Output is correct
76 Correct 1086 ms 586852 KB Output is correct
77 Correct 1010 ms 510720 KB Output is correct
78 Correct 1194 ms 477268 KB Output is correct
79 Correct 1160 ms 495304 KB Output is correct
80 Correct 1932 ms 598532 KB Output is correct
81 Correct 1263 ms 493424 KB Output is correct
82 Correct 1728 ms 559404 KB Output is correct
83 Correct 2058 ms 625332 KB Output is correct
84 Correct 1203 ms 475452 KB Output is correct
85 Correct 1887 ms 609400 KB Output is correct
86 Correct 1845 ms 599980 KB Output is correct
87 Correct 628 ms 428664 KB Output is correct
88 Correct 982 ms 510292 KB Output is correct
89 Correct 1028 ms 510588 KB Output is correct
90 Correct 1027 ms 510280 KB Output is correct