Submission #1108667

#TimeUsernameProblemLanguageResultExecution timeMemory
1108667LudisseyMosaic (IOI24_mosaic)C++17
Compilation error
0 ms0 KiB
#include "mosaic.h" #include <bits/stdc++.h> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; int q,n; vector<vector<int>> lft; vector<vector<int>> top; vector<int> dia; vector<int> diapref; vector<int> diaSpref; vector<int> diaSprefINV; // X cest le top // Y cest la gauche // [le x][le y] int todia(int x, int y){ return (n-x-1)+y; } int prefL(int l, int r, int t ,int b){ if(l>r||t>b) return 0; int sm=lft[r][b]; if(l>0) sm-=lft[l-1][b]; if(t>0) sm-=lft[r][t-1]; if(l>0&&t>0) sm+=lft[l-1][t-1]; return sm; } int prefT(int l, int r, int t ,int b){ if(l>r||t>b) return 0; int sm=top[r][b]; if(l>0) sm-=top[l-1][b]; if(t>0) sm-=top[r][t-1]; if(l>0&&t>0) sm+=top[l-1][t-1]; return sm; } int SprefINV(int l, int r){ int sm=diaSprefINV[l]; if(r<sz(dia)-1) sm-=diaSprefINV[r+1]; int p=diapref[r]; if(l>0) p-=diapref[l-1]; sm-=p*(sz(dia)-(r+1)); return sm; } int Spref(int l, int r){ int sm=diaSpref[r]; if(l>0) sm-=diaSpref[l-1]; int p=diapref[r]; if(l>0) p-=diapref[l-1]; sm-=p*l; return sm; } std::vector<long long> mosaic(std::vector<signed> X, std::vector<signed> Y, std::vector<signed> T, std::vector<signed> B,std::vector<signed> L, std::vector<signed> R) { q = sz(T); n=sz(Y); lft.resize(3,vector<int>(n,0)); top.resize(n,vector<int>(3,0)); dia.resize(n+n-1,0); diaSprefINV.resize(n+n+4,0); diaSpref.resize(n+n+4,0); diapref.resize(n+n+4,0); for (int i = 0; i < n; i++) { lft[0][i]=Y[i]; top[i][0]=X[i]; } if(n>1){ lft[1][0]=X[1]; top[0][1]=Y[1]; if(n>2){ lft[2][0]=X[2]; top[0][2]=Y[2]; } } for (int i = 1; i < n&&n>1; i++) { top[i][1]=(top[i-1][1]==0&&top[i][0]==0); lft[1][i]=(lft[1][i-1]==0&&lft[0][i]==0); } for (int i = 1; i < n&&n>2; i++) { top[i][2]=(top[i-1][2]==0&&top[i][1]==0); lft[2][i]=(lft[2][i-1]==0&&lft[1][i]==0); dia[todia(i,2)]=top[i][2]; dia[todia(2,i)]=lft[2][i]; } for (int i = 0; i < n; i++){ for (int j = 0; j < min(n,3LL); j++) { if(j>0) top[i][j]+=top[i][j-1]; if(i>0) top[i][j]+=top[i-1][j]; if(i>0&&j>0) top[i][j]-=top[i-1][j-1]; if(j>0) lft[j][i]+=lft[j-1][i]; if(i>0) lft[j][i]+=lft[j][i-1]; if(i>0&&j>0) lft[j][i]-=lft[j-1][i-1]; } } for (int i = 0; i < sz(dia); i++) { diapref[i]=dia[i]; diaSpref[i]=dia[i]*(i+1); if(i>0) diapref[i]+=diapref[i-1]; if(i>0) diaSpref[i]+=diaSpref[i-1]; // -- int j=(sz(dia)-(i+1)); diaSprefINV[j]=dia[j]*(sz(dia)-(j)); if(j<sz(dia)-1) diaSprefINV[j]+=diaSprefINV[j+1]; } std::vector<long long> C(q, 0); for (int i = 0; i < q; i++) { int _l=L[i],r=R[i],_t=T[i],b=B[i]; int l=max(3LL,_l); int t=max(3LL,_t); int sm=prefT(_l,r,_t,min(2LL,b)); sm+=prefL(_l,min(2LL,r),_t,b); sm-=prefL(_l,min(2LL,r),_t,min(2LL,b)); if(l>r||t>b) { C[i]=sm; continue; } int lng=min(r-l,b-t); sm+=SprefINV(todia(l,b)-lng,todia(l,b)); sm+=Spref(todia(r,t),todia(r,t)+lng); if((r-l)==(b-t)) sm-=dia[todia(l,t)]*(lng+1); else{ int dp=diapref[todia(l,b)-lng-1]-diapref[todia(r,t)+lng]; sm+=(dp)*(lng+1); } C[i]=sm; } return C; }

Compilation message (stderr)

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:97:34: error: no matching function for call to 'min(int&, long long int)'
   97 |     for (int j = 0; j < min(n,3LL); j++)
      |                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
mosaic.cpp:97:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   97 |     for (int j = 0; j < min(n,3LL); j++)
      |                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
mosaic.cpp:97:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   97 |     for (int j = 0; j < min(n,3LL); j++)
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
mosaic.cpp:97:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   97 |     for (int j = 0; j < min(n,3LL); j++)
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
mosaic.cpp:97:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   97 |     for (int j = 0; j < min(n,3LL); j++)
      |                                  ^
mosaic.cpp:124:21: error: no matching function for call to 'max(long long int, int&)'
  124 |     int l=max(3LL,_l);
      |                     ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
mosaic.cpp:124:21: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  124 |     int l=max(3LL,_l);
      |                     ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
mosaic.cpp:124:21: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  124 |     int l=max(3LL,_l);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
mosaic.cpp:124:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  124 |     int l=max(3LL,_l);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
mosaic.cpp:124:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  124 |     int l=max(3LL,_l);
      |                     ^
mosaic.cpp:125:21: error: no matching function for call to 'max(long long int, int&)'
  125 |     int t=max(3LL,_t);
      |                     ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
mosaic.cpp:125:21: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  125 |     int t=max(3LL,_t);
      |                     ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
mosaic.cpp:125:21: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  125 |     int t=max(3LL,_t);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
mosaic.cpp:125:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  125 |     int t=max(3LL,_t);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
mosaic.cpp:125:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  125 |     int t=max(3LL,_t);
      |                     ^
mosaic.cpp:126:35: error: no matching function for call to 'min(long long int, int&)'
  126 |     int sm=prefT(_l,r,_t,min(2LL,b));
      |                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
mosaic.cpp:126:35: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  126 |     int sm=prefT(_l,r,_t,min(2LL,b));
      |                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
mosaic.cpp:126:35: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  126 |     int sm=prefT(_l,r,_t,min(2LL,b));
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
mosaic.cpp:126:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  126 |     int sm=prefT(_l,r,_t,min(2LL,b));
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
mosaic.cpp:126:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  126 |     int sm=prefT(_l,r,_t,min(2LL,b));
      |                                   ^
mosaic.cpp:127:27: error: no matching function for call to 'min(long long int, int&)'
  127 |     sm+=prefL(_l,min(2LL,r),_t,b);
      |                           ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
mosaic.cpp:127:27: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  127 |     sm+=prefL(_l,min(2LL,r),_t,b);
      |                           ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
mosaic.cpp:127:27: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  127 |     sm+=prefL(_l,min(2LL,r),_t,b);
      |                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
mosaic.cpp:127:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  127 |     sm+=prefL(_l,min(2LL,r),_t,b);
      |                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
mosaic.cpp:127:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  127 |     sm+=prefL(_l,min(2LL,r),_t,b);
      |                           ^
mosaic.cpp:128:27: error: no matching function for call to 'min(long long int, int&)'
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                           ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
mosaic.cpp:128:27: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                           ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
mosaic.cpp:128:27: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
mosaic.cpp:128:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mosaic.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
mosaic.cpp:128:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                           ^
mosaic.cpp:128:41: error: no matching function for call to 'min(long long int, int&)'
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                                         ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
mosaic.cpp:128:41: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  128 |     sm-=prefL(_l,min(2LL,r),_t,min(2LL,b));
      |                                         ^
In file included from /usr/include/c++/10/vector:60,
                 from mosaic.h:1,
                 from mosaic.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278