oj.uz

Submission #969286

# Submission time Handle Problem Language Result Execution time Memory
969286 2024-04-24T21:47:27 Z NemanjaSo2005 Rectangles (IOI19_rect) C++17
72 / 100
 4358 ms 1048576 KB 
#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2505;
ll res=0;
int N,M,mat[maxn][maxn];
int L[maxn],R[maxn];
stack<int> S;
map<pair<int,int>,int> mapa[maxn];
vector<pair<int,int>> getinterval(vector<int> V){
   vector<pair<int,int>> res;
   while(S.size())
      S.pop();
   S.push(0);
   L[0]=-1;
   for(int i=1;i<V.size();i++){
      while(S.size()){
         if(V[S.top()]>V[i])
            break;
         S.pop();
      }
      if(S.size()==0)
         L[i]=-1;
      else
         L[i]=S.top()+1;
      S.push(i);
   }
   while(S.size())
      S.pop();


   S.push(V.size()-1);
   for(int i=V.size()-2;i>=1;i--){
      while(S.size()){
         if(V[S.top()]>V[i])
            break;
         S.pop();
      }
      if(S.size()==0)
         R[i]=-1;
      else
         R[i]=S.top()-1;
      S.push(i);
   }

   for(int i=1;i<V.size()-1;i++){
      if(L[i]==-1)
         continue;
      if(R[i]==-1)
         continue;
      res.push_back({L[i],R[i]});
   }
   vector<pair<int,int>> r2;
   if(res.size()){
      sort(res.begin(),res.end());
      r2.push_back(res[0]);
      for(int i=1;i<res.size();i++)
         if(res[i]!=res[i-1])
            r2.push_back(res[i]);
   }
   return r2;
}
struct slog{
   int duz,kol;
} pp;
bool poduz(slog a,slog b){
   return a.duz<b.duz;
}
bool pokol(slog a,slog b){
   return a.kol<b.kol;
}
vector<slog> vert[maxn][maxn],hor[maxn][maxn];
int fwt[maxn];
void add(int x,int kol){
   x++;
   for(int i=x;i<=2501;i+=i&-i)
      fwt[i]+=kol;
}
int sum(int x){
   int r=0;
   x++;
   for(int i=x;i>=1;i-=i&-i)
      r+=fwt[i];
   return r;
}
ll resi(vector<slog> A,vector<slog> B){
   ll ret=0;
   sort(A.begin(),A.end(),poduz);
   sort(B.begin(),B.end(),pokol);

   for(int i=0;i<B.size();i++)
      add(B[i].duz,1);
   int pok=0;

   for(int i=0;i<A.size();i++){
      while(pok<B.size()){
         if(B[pok].kol>=A[i].duz)
            break;
         add(B[pok].duz,-1);
         pok++;
      }
      ret+=sum(A[i].kol);
   }

   while(pok<B.size()){
      add(B[pok].duz,-1);
      pok++;
   }
/*
   for(slog x:A)
      for(slog y:B){
         if(x.duz>y.kol)
            continue;
         if(y.duz>x.kol)
            continue;
         ret++;
      }*/
   return ret;
}
ll count_rectangles(std::vector<std::vector<int> > inp) {
	N=inp.size();
	M=inp[0].size();
   for(int i=0;i<N;i++)
      for(int j=0;j<M;j++)
         mat[i][j]=inp[i][j];


   /// Vertikalni
   for(int i=N-2;i>=1;i--){
      vector<int> V;
      for(int j=0;j<M;j++)
         V.push_back(mat[i][j]);
      auto I = getinterval(V);
      for(auto x:I){
         if(mapa[i+1].find(x)!=mapa[i+1].end())
            mapa[i][x]=mapa[i+1][x]+1;
         else
            mapa[i][x]=1;

         pp.kol=mapa[i][x];
         pp.duz=x.second-x.first+1;
         vert[i][x.first].push_back(pp);
      }
   }

   /// Horizontalni

   for(int i=0;i<=M;i++)
      mapa[i].clear();
   for(int i=M-2;i>=1;i--){
      vector<int> V;
      for(int j=0;j<N;j++)
         V.push_back(mat[j][i]);
      auto I = getinterval(V);
      for(auto x:I){
         if(mapa[i+1].find(x)!=mapa[i+1].end())
            mapa[i][x]=mapa[i+1][x]+1;
         else
            mapa[i][x]=1;

         pp.kol=mapa[i][x];
         pp.duz=x.second-x.first+1;
         hor[x.first][i].push_back(pp);
      }
   }

   ll res=0;
   for(int i=1;i<=N-2;i++)
      for(int j=1;j<=M-2;j++){
       //  cout<<i<<" "<<j<<endl;
         res+=resi(vert[i][j],hor[i][j]);
      }

   return res;
}

Compilation message

rect.cpp: In function 'std::vector<std::pair<int, int> > getinterval(std::vector<int>)':
rect.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    for(int i=1;i<V.size();i++){
      |                ~^~~~~~~~~
rect.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i=1;i<V.size()-1;i++){
      |                ~^~~~~~~~~~~
rect.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |       for(int i=1;i<res.size();i++)
      |                   ~^~~~~~~~~~~
rect.cpp: In function 'long long int resi(std::vector<slog>, std::vector<slog>)':
rect.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int i=0;i<B.size();i++)
      |                ~^~~~~~~~~
rect.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int i=0;i<A.size();i++){
      |                ~^~~~~~~~~
rect.cpp:97:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       while(pok<B.size()){
      |             ~~~^~~~~~~~~
rect.cpp:106:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    while(pok<B.size()){
      |          ~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 295972 KB Output is correct
2 Correct 109 ms 296020 KB Output is correct
3 Correct 109 ms 296020 KB Output is correct
4 Correct 109 ms 296020 KB Output is correct
5 Correct 109 ms 296268 KB Output is correct
6 Correct 107 ms 296020 KB Output is correct
7 Correct 107 ms 296016 KB Output is correct
8 Correct 111 ms 295920 KB Output is correct
9 Correct 113 ms 296204 KB Output is correct
10 Correct 111 ms 296020 KB Output is correct
11 Correct 108 ms 296116 KB Output is correct
12 Correct 113 ms 296000 KB Output is correct
13 Correct 112 ms 296056 KB Output is correct
14 Correct 108 ms 296020 KB Output is correct
15 Correct 109 ms 296044 KB Output is correct
16 Correct 109 ms 296020 KB Output is correct
17 Correct 108 ms 296012 KB Output is correct
18 Correct 109 ms 295980 KB Output is correct
19 Correct 110 ms 295884 KB Output is correct
20 Correct 110 ms 295936 KB Output is correct
21 Correct 110 ms 296016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 295972 KB Output is correct
2 Correct 109 ms 296020 KB Output is correct
3 Correct 109 ms 296020 KB Output is correct
4 Correct 109 ms 296020 KB Output is correct
5 Correct 109 ms 296268 KB Output is correct
6 Correct 107 ms 296020 KB Output is correct
7 Correct 107 ms 296016 KB Output is correct
8 Correct 111 ms 295920 KB Output is correct
9 Correct 113 ms 296204 KB Output is correct
10 Correct 111 ms 296020 KB Output is correct
11 Correct 108 ms 296116 KB Output is correct
12 Correct 113 ms 296000 KB Output is correct
13 Correct 112 ms 296056 KB Output is correct
14 Correct 108 ms 296020 KB Output is correct
15 Correct 109 ms 296044 KB Output is correct
16 Correct 109 ms 296020 KB Output is correct
17 Correct 108 ms 296012 KB Output is correct
18 Correct 109 ms 295980 KB Output is correct
19 Correct 110 ms 295884 KB Output is correct
20 Correct 110 ms 295936 KB Output is correct
21 Correct 110 ms 296016 KB Output is correct
22 Correct 113 ms 296672 KB Output is correct
23 Correct 113 ms 296900 KB Output is correct
24 Correct 115 ms 296788 KB Output is correct
25 Correct 114 ms 296276 KB Output is correct
26 Correct 114 ms 296528 KB Output is correct
27 Correct 113 ms 296528 KB Output is correct
28 Correct 113 ms 296532 KB Output is correct
29 Correct 112 ms 296196 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 295972 KB Output is correct
2 Correct 109 ms 296020 KB Output is correct
3 Correct 109 ms 296020 KB Output is correct
4 Correct 109 ms 296020 KB Output is correct
5 Correct 109 ms 296268 KB Output is correct
6 Correct 107 ms 296020 KB Output is correct
7 Correct 107 ms 296016 KB Output is correct
8 Correct 111 ms 295920 KB Output is correct
9 Correct 113 ms 296204 KB Output is correct
10 Correct 111 ms 296020 KB Output is correct
11 Correct 108 ms 296116 KB Output is correct
12 Correct 113 ms 296000 KB Output is correct
13 Correct 112 ms 296056 KB Output is correct
14 Correct 108 ms 296020 KB Output is correct
15 Correct 109 ms 296044 KB Output is correct
16 Correct 109 ms 296020 KB Output is correct
17 Correct 113 ms 296672 KB Output is correct
18 Correct 113 ms 296900 KB Output is correct
19 Correct 115 ms 296788 KB Output is correct
20 Correct 114 ms 296276 KB Output is correct
21 Correct 114 ms 296528 KB Output is correct
22 Correct 113 ms 296528 KB Output is correct
23 Correct 113 ms 296532 KB Output is correct
24 Correct 112 ms 296196 KB Output is correct
25 Correct 108 ms 296012 KB Output is correct
26 Correct 109 ms 295980 KB Output is correct
27 Correct 110 ms 295884 KB Output is correct
28 Correct 110 ms 295936 KB Output is correct
29 Correct 110 ms 296016 KB Output is correct
30 Correct 132 ms 301904 KB Output is correct
31 Correct 137 ms 302076 KB Output is correct
32 Correct 134 ms 301972 KB Output is correct
33 Correct 121 ms 298580 KB Output is correct
34 Correct 140 ms 300708 KB Output is correct
35 Correct 143 ms 300924 KB Output is correct
36 Correct 139 ms 300628 KB Output is correct
37 Correct 141 ms 300628 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 295972 KB Output is correct
2 Correct 109 ms 296020 KB Output is correct
3 Correct 109 ms 296020 KB Output is correct
4 Correct 109 ms 296020 KB Output is correct
5 Correct 109 ms 296268 KB Output is correct
6 Correct 107 ms 296020 KB Output is correct
7 Correct 107 ms 296016 KB Output is correct
8 Correct 111 ms 295920 KB Output is correct
9 Correct 113 ms 296204 KB Output is correct
10 Correct 111 ms 296020 KB Output is correct
11 Correct 108 ms 296116 KB Output is correct
12 Correct 113 ms 296000 KB Output is correct
13 Correct 112 ms 296056 KB Output is correct
14 Correct 108 ms 296020 KB Output is correct
15 Correct 109 ms 296044 KB Output is correct
16 Correct 109 ms 296020 KB Output is correct
17 Correct 113 ms 296672 KB Output is correct
18 Correct 113 ms 296900 KB Output is correct
19 Correct 115 ms 296788 KB Output is correct
20 Correct 114 ms 296276 KB Output is correct
21 Correct 114 ms 296528 KB Output is correct
22 Correct 113 ms 296528 KB Output is correct
23 Correct 113 ms 296532 KB Output is correct
24 Correct 112 ms 296196 KB Output is correct
25 Correct 132 ms 301904 KB Output is correct
26 Correct 137 ms 302076 KB Output is correct
27 Correct 134 ms 301972 KB Output is correct
28 Correct 121 ms 298580 KB Output is correct
29 Correct 140 ms 300708 KB Output is correct
30 Correct 143 ms 300924 KB Output is correct
31 Correct 139 ms 300628 KB Output is correct
32 Correct 141 ms 300628 KB Output is correct
33 Correct 108 ms 296012 KB Output is correct
34 Correct 109 ms 295980 KB Output is correct
35 Correct 110 ms 295884 KB Output is correct
36 Correct 110 ms 295936 KB Output is correct
37 Correct 110 ms 296016 KB Output is correct
38 Correct 303 ms 337416 KB Output is correct
39 Correct 289 ms 331920 KB Output is correct
40 Correct 265 ms 331584 KB Output is correct
41 Correct 245 ms 327008 KB Output is correct
42 Correct 500 ms 366848 KB Output is correct
43 Correct 500 ms 367068 KB Output is correct
44 Correct 499 ms 366928 KB Output is correct
45 Correct 463 ms 360600 KB Output is correct
46 Correct 245 ms 319268 KB Output is correct
47 Correct 297 ms 325972 KB Output is correct
48 Correct 566 ms 352236 KB Output is correct
49 Correct 570 ms 352644 KB Output is correct
50 Correct 317 ms 332612 KB Output is correct
51 Correct 357 ms 323796 KB Output is correct
52 Correct 535 ms 348800 KB Output is correct
53 Correct 553 ms 348964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 296272 KB Output is correct
2 Correct 110 ms 296276 KB Output is correct
3 Correct 108 ms 296004 KB Output is correct
4 Correct 109 ms 295916 KB Output is correct
5 Correct 110 ms 296216 KB Output is correct
6 Correct 110 ms 296276 KB Output is correct
7 Correct 114 ms 296308 KB Output is correct
8 Correct 110 ms 296196 KB Output is correct
9 Correct 111 ms 296324 KB Output is correct
10 Correct 108 ms 295872 KB Output is correct
11 Correct 122 ms 296024 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 296012 KB Output is correct
2 Correct 109 ms 295980 KB Output is correct
3 Correct 110 ms 295884 KB Output is correct
4 Correct 110 ms 295936 KB Output is correct
5 Correct 110 ms 296016 KB Output is correct
6 Correct 107 ms 296020 KB Output is correct
7 Correct 932 ms 419288 KB Output is correct
8 Correct 1959 ms 562984 KB Output is correct
9 Correct 1966 ms 564176 KB Output is correct
10 Correct 1958 ms 564224 KB Output is correct
11 Correct 252 ms 331644 KB Output is correct
12 Correct 374 ms 365652 KB Output is correct
13 Correct 378 ms 368932 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 295972 KB Output is correct
2 Correct 109 ms 296020 KB Output is correct
3 Correct 109 ms 296020 KB Output is correct
4 Correct 109 ms 296020 KB Output is correct
5 Correct 109 ms 296268 KB Output is correct
6 Correct 107 ms 296020 KB Output is correct
7 Correct 107 ms 296016 KB Output is correct
8 Correct 111 ms 295920 KB Output is correct
9 Correct 113 ms 296204 KB Output is correct
10 Correct 111 ms 296020 KB Output is correct
11 Correct 108 ms 296116 KB Output is correct
12 Correct 113 ms 296000 KB Output is correct
13 Correct 112 ms 296056 KB Output is correct
14 Correct 108 ms 296020 KB Output is correct
15 Correct 109 ms 296044 KB Output is correct
16 Correct 109 ms 296020 KB Output is correct
17 Correct 113 ms 296672 KB Output is correct
18 Correct 113 ms 296900 KB Output is correct
19 Correct 115 ms 296788 KB Output is correct
20 Correct 114 ms 296276 KB Output is correct
21 Correct 114 ms 296528 KB Output is correct
22 Correct 113 ms 296528 KB Output is correct
23 Correct 113 ms 296532 KB Output is correct
24 Correct 112 ms 296196 KB Output is correct
25 Correct 132 ms 301904 KB Output is correct
26 Correct 137 ms 302076 KB Output is correct
27 Correct 134 ms 301972 KB Output is correct
28 Correct 121 ms 298580 KB Output is correct
29 Correct 140 ms 300708 KB Output is correct
30 Correct 143 ms 300924 KB Output is correct
31 Correct 139 ms 300628 KB Output is correct
32 Correct 141 ms 300628 KB Output is correct
33 Correct 303 ms 337416 KB Output is correct
34 Correct 289 ms 331920 KB Output is correct
35 Correct 265 ms 331584 KB Output is correct
36 Correct 245 ms 327008 KB Output is correct
37 Correct 500 ms 366848 KB Output is correct
38 Correct 500 ms 367068 KB Output is correct
39 Correct 499 ms 366928 KB Output is correct
40 Correct 463 ms 360600 KB Output is correct
41 Correct 245 ms 319268 KB Output is correct
42 Correct 297 ms 325972 KB Output is correct
43 Correct 566 ms 352236 KB Output is correct
44 Correct 570 ms 352644 KB Output is correct
45 Correct 317 ms 332612 KB Output is correct
46 Correct 357 ms 323796 KB Output is correct
47 Correct 535 ms 348800 KB Output is correct
48 Correct 553 ms 348964 KB Output is correct
49 Correct 113 ms 296272 KB Output is correct
50 Correct 110 ms 296276 KB Output is correct
51 Correct 108 ms 296004 KB Output is correct
52 Correct 109 ms 295916 KB Output is correct
53 Correct 110 ms 296216 KB Output is correct
54 Correct 110 ms 296276 KB Output is correct
55 Correct 114 ms 296308 KB Output is correct
56 Correct 110 ms 296196 KB Output is correct
57 Correct 111 ms 296324 KB Output is correct
58 Correct 108 ms 295872 KB Output is correct
59 Correct 122 ms 296024 KB Output is correct
60 Correct 107 ms 296020 KB Output is correct
61 Correct 932 ms 419288 KB Output is correct
62 Correct 1959 ms 562984 KB Output is correct
63 Correct 1966 ms 564176 KB Output is correct
64 Correct 1958 ms 564224 KB Output is correct
65 Correct 252 ms 331644 KB Output is correct
66 Correct 374 ms 365652 KB Output is correct
67 Correct 378 ms 368932 KB Output is correct
68 Correct 108 ms 296012 KB Output is correct
69 Correct 109 ms 295980 KB Output is correct
70 Correct 110 ms 295884 KB Output is correct
71 Correct 110 ms 295936 KB Output is correct
72 Correct 110 ms 296016 KB Output is correct
73 Correct 2993 ms 760176 KB Output is correct
74 Correct 2886 ms 693052 KB Output is correct
75 Correct 2422 ms 693580 KB Output is correct
76 Correct 2039 ms 630308 KB Output is correct
77 Runtime error 4358 ms 1048576 KB Execution killed with signal 9
78 Halted 0 ms 0 KB -