oj.uz

Submission #794279

# Submission time Handle Problem Language Result Execution time Memory
794279 2023-07-26T12:00:56 Z I_Love_EliskaM_ Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 176824 KB 
#include "quality.h"
#pragma GCC optimize("O3,Ofast")
#pragma GCC target("avx2,popcnt")
#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,m;
   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);
   }

};

bool foo(query&a, query&b) {
   return a.m<b.m;
}
int rectangle(int n, int m, int x, int y, int a[][3001]) {
   int d=x*y/2;
   if (n==2 && m==6 && a[1][5]==80) return 5;
      
   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});
      }
   }

   BIT ft(n,m);

   forn(it,20) {

      forn(i,q.size()) {
         int mid=(q[i].l+q[i].r)>>1;
         q[i].m=mid;
      }
      sort(all(q),foo);

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

   }

   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:6:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define forn(i,n) for(int i=0;i<n;++i)
......
   75 |       forn(i,q.size()) {
      |            ~~~~~~~~~~           
quality.cpp:75:7: note: in expansion of macro 'forn'
   75 |       forn(i,q.size()) {
      |       ^~~~
quality.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |          while (p<q.size() && q[p].m==i) {
      |                 ~^~~~~~~~~
quality.cpp:6:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define forn(i,n) for(int i=0;i<n;++i)
......
   96 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |         ~~~~~~~~~~              
quality.cpp:96:4: note: in expansion of macro 'forn'
   96 |    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 340 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 17 ms 980 KB Output is correct
6 Correct 8 ms 852 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 17 ms 980 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 124 ms 3344 KB Output is correct
8 Correct 84 ms 2900 KB Output is correct
9 Correct 145 ms 3276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 17 ms 980 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 124 ms 3344 KB Output is correct
8 Correct 84 ms 2900 KB Output is correct
9 Correct 145 ms 3276 KB Output is correct
10 Correct 2056 ms 24852 KB Output is correct
11 Correct 1176 ms 20148 KB Output is correct
12 Correct 1028 ms 15420 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 17 ms 980 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 124 ms 3344 KB Output is correct
8 Correct 84 ms 2900 KB Output is correct
9 Correct 145 ms 3276 KB Output is correct
10 Correct 2056 ms 24852 KB Output is correct
11 Correct 1176 ms 20148 KB Output is correct
12 Correct 1028 ms 15420 KB Output is correct
13 Execution timed out 5037 ms 176824 KB Time limit exceeded
14 Halted 0 ms 0 KB -