oj.uz

Submission #987242

# Submission time Handle Problem Language Result Execution time Memory
987242 2024-05-22T12:21:35 Z AdamGS Rectangles (IOI19_rect) C++17
0 / 100
 161 ms 295764 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;
vector<pair<int,int>>lewo[LIM][LIM], gora[LIM][LIM];
ll count_rectangles(vector<vector<int>>A) {
  int n=A.size(), m=A[0].size();
  rep(i, n) {
    vector<int>P;
    rep(j, m) {
      while(P.size()>0 && A[i][P.back()]<=A[i][j]) {
        P.pop_back();
        if(P.size()) 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) {
      while(P.size()>0 && A[P.back()][j]<=A[i][j]) {
        P.pop_back();
        if(P.size()) 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-1) rep(j, m-1) {
    for(auto a : lewo[i][j+1]) {
      for(auto b : gora[i+1][j]) {
        if(a.nd>=b.st && b.nd>=a.st) ++ans;
      }
    }
  }
  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:24:7: note: in expansion of macro 'rep'
   24 |       rep(a, lewo[i][j].size()) {
      |       ^~~
rect.cpp:25: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]
   25 |         while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:26: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]
   26 |         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:40:7: note: in expansion of macro 'rep'
   40 |       rep(a, gora[i][j].size()) {
      |       ^~~
rect.cpp:41: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]
   41 |         while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:42: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]
   42 |         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;
      |            ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 295508 KB Output is correct
2 Correct 157 ms 295620 KB Output is correct
3 Correct 158 ms 295576 KB Output is correct
4 Correct 161 ms 295508 KB Output is correct
5 Correct 159 ms 295428 KB Output is correct
6 Correct 157 ms 295552 KB Output is correct
7 Correct 157 ms 295580 KB Output is correct
8 Correct 159 ms 295504 KB Output is correct
9 Incorrect 158 ms 295504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 295508 KB Output is correct
2 Correct 157 ms 295620 KB Output is correct
3 Correct 158 ms 295576 KB Output is correct
4 Correct 161 ms 295508 KB Output is correct
5 Correct 159 ms 295428 KB Output is correct
6 Correct 157 ms 295552 KB Output is correct
7 Correct 157 ms 295580 KB Output is correct
8 Correct 159 ms 295504 KB Output is correct
9 Incorrect 158 ms 295504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 295508 KB Output is correct
2 Correct 157 ms 295620 KB Output is correct
3 Correct 158 ms 295576 KB Output is correct
4 Correct 161 ms 295508 KB Output is correct
5 Correct 159 ms 295428 KB Output is correct
6 Correct 157 ms 295552 KB Output is correct
7 Correct 157 ms 295580 KB Output is correct
8 Correct 159 ms 295504 KB Output is correct
9 Incorrect 158 ms 295504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 295508 KB Output is correct
2 Correct 157 ms 295620 KB Output is correct
3 Correct 158 ms 295576 KB Output is correct
4 Correct 161 ms 295508 KB Output is correct
5 Correct 159 ms 295428 KB Output is correct
6 Correct 157 ms 295552 KB Output is correct
7 Correct 157 ms 295580 KB Output is correct
8 Correct 159 ms 295504 KB Output is correct
9 Incorrect 158 ms 295504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 295636 KB Output is correct
2 Correct 159 ms 295764 KB Output is correct
3 Correct 161 ms 295508 KB Output is correct
4 Correct 155 ms 295440 KB Output is correct
5 Correct 139 ms 295760 KB Output is correct
6 Correct 159 ms 295760 KB Output is correct
7 Correct 141 ms 295764 KB Output is correct
8 Correct 161 ms 295764 KB Output is correct
9 Incorrect 143 ms 295764 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 295508 KB Output is correct
2 Correct 157 ms 295620 KB Output is correct
3 Correct 158 ms 295576 KB Output is correct
4 Correct 161 ms 295508 KB Output is correct
5 Correct 159 ms 295428 KB Output is correct
6 Correct 157 ms 295552 KB Output is correct
7 Correct 157 ms 295580 KB Output is correct
8 Correct 159 ms 295504 KB Output is correct
9 Incorrect 158 ms 295504 KB Output isn't correct
10 Halted 0 ms 0 KB -