oj.uz

Submission #969285

# Submission time Handle Problem Language Result Execution time Memory
969285 2024-04-24T21:45:39 Z NemanjaSo2005 Rectangles (IOI19_rect) C++17
13 / 100
 2032 ms 564208 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=A.size()-1;i>=0;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: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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 296008 KB Output is correct
2 Correct 112 ms 296032 KB Output is correct
3 Correct 115 ms 295968 KB Output is correct
4 Correct 118 ms 296020 KB Output is correct
5 Correct 111 ms 296072 KB Output is correct
6 Incorrect 110 ms 296136 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 296008 KB Output is correct
2 Correct 112 ms 296032 KB Output is correct
3 Correct 115 ms 295968 KB Output is correct
4 Correct 118 ms 296020 KB Output is correct
5 Correct 111 ms 296072 KB Output is correct
6 Incorrect 110 ms 296136 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 296008 KB Output is correct
2 Correct 112 ms 296032 KB Output is correct
3 Correct 115 ms 295968 KB Output is correct
4 Correct 118 ms 296020 KB Output is correct
5 Correct 111 ms 296072 KB Output is correct
6 Incorrect 110 ms 296136 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 296008 KB Output is correct
2 Correct 112 ms 296032 KB Output is correct
3 Correct 115 ms 295968 KB Output is correct
4 Correct 118 ms 296020 KB Output is correct
5 Correct 111 ms 296072 KB Output is correct
6 Incorrect 110 ms 296136 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 296332 KB Output is correct
2 Correct 118 ms 296288 KB Output is correct
3 Correct 113 ms 296016 KB Output is correct
4 Correct 108 ms 296016 KB Output is correct
5 Incorrect 110 ms 296324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 296016 KB Output is correct
2 Correct 944 ms 419512 KB Output is correct
3 Correct 2032 ms 562988 KB Output is correct
4 Correct 1973 ms 564140 KB Output is correct
5 Correct 1987 ms 564208 KB Output is correct
6 Correct 233 ms 331448 KB Output is correct
7 Correct 368 ms 365876 KB Output is correct
8 Correct 401 ms 369064 KB Output is correct
9 Correct 111 ms 296016 KB Output is correct
10 Correct 111 ms 295940 KB Output is correct
11 Correct 109 ms 296016 KB Output is correct
12 Correct 109 ms 296016 KB Output is correct
13 Correct 107 ms 296020 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 296008 KB Output is correct
2 Correct 112 ms 296032 KB Output is correct
3 Correct 115 ms 295968 KB Output is correct
4 Correct 118 ms 296020 KB Output is correct
5 Correct 111 ms 296072 KB Output is correct
6 Incorrect 110 ms 296136 KB Output isn't correct
7 Halted 0 ms 0 KB -