oj.uz

답안 #794242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794242 2023-07-26T11:22:51 Z I_Love_EliskaM_ 삶의 질 (IOI10_quality) C++14
80 / 100
 2449 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});
      }
   }

   vector<vector<query2>> s(n*m+1);
   BIT ft(n,m);
   forn(it,20) {

      forn(i,q.size()) {
         int mid=(q[i].l+q[i].r)>>1;
         s[mid].pb({q[i].i,q[i].j,i});
      }

      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; 
         }
         s[i].clear();
      }
      for (int i=1; i<=n*m; ++i) {
         ft.add(pos[i].f,pos[i].s,-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)
......
   69 |       forn(i,q.size()) {
      |            ~~~~~~~~~~           
quality.cpp:69:7: note: in expansion of macro 'forn'
   69 |       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)
......
   90 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |         ~~~~~~~~~~              
quality.cpp:90:4: note: in expansion of macro 'forn'
   90 |    forn(i,q.size()) ans=min(ans,q[i].r);
      |    ^~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 1364 KB Output is correct
5 Correct 20 ms 2008 KB Output is correct
6 Correct 12 ms 1140 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 1364 KB Output is correct
5 Correct 20 ms 2008 KB Output is correct
6 Correct 12 ms 1140 KB Output is correct
7 Correct 174 ms 9576 KB Output is correct
8 Correct 127 ms 5116 KB Output is correct
9 Correct 157 ms 10792 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 1364 KB Output is correct
5 Correct 20 ms 2008 KB Output is correct
6 Correct 12 ms 1140 KB Output is correct
7 Correct 174 ms 9576 KB Output is correct
8 Correct 127 ms 5116 KB Output is correct
9 Correct 157 ms 10792 KB Output is correct
10 Correct 2449 ms 119396 KB Output is correct
11 Correct 1881 ms 45744 KB Output is correct
12 Correct 1263 ms 67368 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 1364 KB Output is correct
5 Correct 20 ms 2008 KB Output is correct
6 Correct 12 ms 1140 KB Output is correct
7 Correct 174 ms 9576 KB Output is correct
8 Correct 127 ms 5116 KB Output is correct
9 Correct 157 ms 10792 KB Output is correct
10 Correct 2449 ms 119396 KB Output is correct
11 Correct 1881 ms 45744 KB Output is correct
12 Correct 1263 ms 67368 KB Output is correct
13 Runtime error 993 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -