oj.uz

Submission #794276

# Submission time Handle Problem Language Result Execution time Memory
794276 2023-07-26T11:58:13 Z I_Love_EliskaM_ Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 245896 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,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;
      
   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: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)
......
   72 |       forn(i,q.size()) {
      |            ~~~~~~~~~~           
quality.cpp:72:7: note: in expansion of macro 'forn'
   72 |       forn(i,q.size()) {
      |       ^~~~
quality.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |          while (p<q.size() && q[p].m==i) {
      |                 ~^~~~~~~~~
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)
......
   93 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |         ~~~~~~~~~~              
quality.cpp:93:4: note: in expansion of macro 'forn'
   93 |    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 9 ms 888 KB Output is correct
5 Correct 16 ms 980 KB Output is correct
6 Correct 7 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 9 ms 888 KB Output is correct
5 Correct 16 ms 980 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 109 ms 3344 KB Output is correct
8 Correct 69 ms 2940 KB Output is correct
9 Correct 127 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 9 ms 888 KB Output is correct
5 Correct 16 ms 980 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 109 ms 3344 KB Output is correct
8 Correct 69 ms 2940 KB Output is correct
9 Correct 127 ms 3276 KB Output is correct
10 Correct 1737 ms 24844 KB Output is correct
11 Correct 957 ms 20156 KB Output is correct
12 Correct 853 ms 15400 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 9 ms 888 KB Output is correct
5 Correct 16 ms 980 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 109 ms 3344 KB Output is correct
8 Correct 69 ms 2940 KB Output is correct
9 Correct 127 ms 3276 KB Output is correct
10 Correct 1737 ms 24844 KB Output is correct
11 Correct 957 ms 20156 KB Output is correct
12 Correct 853 ms 15400 KB Output is correct
13 Execution timed out 5014 ms 245896 KB Time limit exceeded
14 Halted 0 ms 0 KB -