Submission #266781

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
266781	2020-08-15 12:53:30	dennisstar	Rectangles (IOI19_rect)	C++17	72 / 100	5076 ms	376968 KiB

rect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "rect.h"
#define eb emplace_back
#define hsh(a, b, c) ((a)*6250000ll+(b)*2500ll+c)
using namespace std;
using ll = long long;
int N, M;
vector<ll> H, V;
long long count_rectangles(vector<vector<int>> a) {
  N=a.size(); M=a[0].size();
  vector<vector<int>> l, r, u, d;
  for (int i=0; i<N; i++)
    l.eb(vector<int>(M, -1));
  r=u=d=l;
  for (int i=1; i<N-1; i++) {
    vector<int> st;
    for (int j=0; j<M; j++) {
      while (st.size()&&a[i][st.back()]<a[i][j]) st.pop_back();
      if (st.size()&&st.back()<j-1) H.eb(hsh(st.back(), j, i));
      st.eb(j);
    }
    st.clear();
    for (int j=M-1; j>=0; j--) {
      while (st.size()&&a[i][st.back()]<a[i][j]) st.pop_back();
      if (st.size()&&st.back()>j+1) H.eb(hsh(j, st.back(), i));
      st.eb(j);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:84:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   if (b1>=H.size()||hsh(L, R, U+1)!=H[b1]) continue;
      |       ~~^~~~~~~~~~
rect.cpp:86:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   if (b1>=H.size()||hsh(L, R, D-1)!=H[b1]) continue;
      |       ~~^~~~~~~~~~
rect.cpp:89:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   if (b1>=V.size()||hsh(U, D, L+1)!=V[b1]) continue;
      |       ~~^~~~~~~~~~
rect.cpp:91:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   if (b1>=V.size()||hsh(U, D, R-1)!=V[b1]) continue;
      |       ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28