oj.uz

Submission #794262

# Submission time Handle Problem Language Result Execution time Memory
794262 2023-07-26T11:40:01 Z I_Love_EliskaM_ Quality Of Living (IOI10_quality) C++14
80 / 100
 1703 ms 262144 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first 
#define s second

struct query {
   int i,j,l,r;
   query(int i, int j, int l, int r) {
      this->i=i,this->j=j,this->l=l,this->r=r;
   }
};
struct query2 {
   int x,y,i;
};

set<int> f,s;

struct BIT {

   vector<vector<int>> t;
   int n,m;
   BIT(int n, int m) {
      this->n=n, this->m=m;
      t.assign(n,vector<int>(m,0));
   }
   void add(int i, int j, int x) {
      for(;i<n;i=i|(i+1)) {
         for(int j2=j;j2<m;j2=j2|(j2+1)) t[i][j2]+=x;
      }
   }

   int sum(int a, int b) {
      int q=0;
      for(;a>=0;a=(a&(a+1))-1) {
         for(int r=b;r>=0;r=(r&(r+1))-1) {
            q+=t[a][r];
         }
      }
      return q;
   }
   int sum(int a, int b, int c, int d) {
      return sum(c,d) - sum(a-1,d) - sum(c,b-1) + sum(a-1,b-1);
   }

};

int rectangle(int n, int m, int x, int y, int a[][3001]) {
   int d=x*y/2;
      
   vector<pi> pos(n*m+1);
   forn(i,n) forn(j,m) pos[a[i][j]]={i,j};

   vector<query> q;
   for(int i=0; i+x<=n; ++i) {
      for (int j=0; j+y<=m; ++j) {
         q.pb({i,j,1,n*m});
      }
   }

   forn(it,20) {

      vector<vector<query2>> s(n*m+1);
      forn(i,q.size()) {
         int mid=(q[i].l+q[i].r)>>1;
         s[mid].pb({q[i].i,q[i].j,i});
      }
      BIT ft(n,m);

      for (int i=1; i<=n*m; ++i) {
         ft.add(pos[i].f,pos[i].s,1);
         for(auto&k:s[i]) {
            int z=ft.sum(k.x,k.y,k.x+x-1,k.y+y-1);
            if (z>=d+1) q[k.i].r=i;
            else q[k.i].l=i+1; 
         }
      }

   }

   int ans=n*m;
   forn(i,q.size()) ans=min(ans,q[i].r);
   return ans;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   68 |       forn(i,q.size()) {
      |            ~~~~~~~~~~           
quality.cpp:68:7: note: in expansion of macro 'forn'
   68 |       forn(i,q.size()) {
      |       ^~~~
quality.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   86 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |         ~~~~~~~~~~              
quality.cpp:86:4: note: in expansion of macro 'forn'
   86 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |    ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 1124 KB Output is correct
5 Correct 14 ms 1248 KB Output is correct
6 Correct 8 ms 1136 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 1124 KB Output is correct
5 Correct 14 ms 1248 KB Output is correct
6 Correct 8 ms 1136 KB Output is correct
7 Correct 113 ms 5664 KB Output is correct
8 Correct 75 ms 5068 KB Output is correct
9 Correct 106 ms 5576 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 1124 KB Output is correct
5 Correct 14 ms 1248 KB Output is correct
6 Correct 8 ms 1136 KB Output is correct
7 Correct 113 ms 5664 KB Output is correct
8 Correct 75 ms 5068 KB Output is correct
9 Correct 106 ms 5576 KB Output is correct
10 Correct 1703 ms 52524 KB Output is correct
11 Correct 1137 ms 43756 KB Output is correct
12 Correct 827 ms 29368 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 1124 KB Output is correct
5 Correct 14 ms 1248 KB Output is correct
6 Correct 8 ms 1136 KB Output is correct
7 Correct 113 ms 5664 KB Output is correct
8 Correct 75 ms 5068 KB Output is correct
9 Correct 106 ms 5576 KB Output is correct
10 Correct 1703 ms 52524 KB Output is correct
11 Correct 1137 ms 43756 KB Output is correct
12 Correct 827 ms 29368 KB Output is correct
13 Runtime error 935 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -