oj.uz

Submission #794237

# Submission time Handle Problem Language Result Execution time Memory
794237 2023-07-26T11:18:46 Z I_Love_EliskaM_ Quality Of Living (IOI10_quality) C++14
80 / 100
 1670 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; 
         }
      }

   }

   //forn(i,q.size()) cout<<q[i].i<<' '<<q[i].j<<": "<<q[i].l<<' '<<q[i].r<<'\n';

   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)
......
   88 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |         ~~~~~~~~~~              
quality.cpp:88:4: note: in expansion of macro 'forn'
   88 |    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 468 KB Output is correct
3 Correct 1 ms 436 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 468 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 14 ms 1244 KB Output is correct
6 Correct 8 ms 1128 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 468 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 14 ms 1244 KB Output is correct
6 Correct 8 ms 1128 KB Output is correct
7 Correct 110 ms 6160 KB Output is correct
8 Correct 75 ms 5592 KB Output is correct
9 Correct 106 ms 6004 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 468 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 14 ms 1244 KB Output is correct
6 Correct 8 ms 1128 KB Output is correct
7 Correct 110 ms 6160 KB Output is correct
8 Correct 75 ms 5592 KB Output is correct
9 Correct 106 ms 6004 KB Output is correct
10 Correct 1670 ms 59232 KB Output is correct
11 Correct 1135 ms 50500 KB Output is correct
12 Correct 825 ms 32596 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 468 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 14 ms 1244 KB Output is correct
6 Correct 8 ms 1128 KB Output is correct
7 Correct 110 ms 6160 KB Output is correct
8 Correct 75 ms 5592 KB Output is correct
9 Correct 106 ms 6004 KB Output is correct
10 Correct 1670 ms 59232 KB Output is correct
11 Correct 1135 ms 50500 KB Output is correct
12 Correct 825 ms 32596 KB Output is correct
13 Runtime error 933 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -