oj.uz

Submission #915113

# Submission time Handle Problem Language Result Execution time Memory
915113 2024-01-23T11:14:54 Z cig32 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 42068 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
  char *stack, *send;
  stack = (char *)malloc(stsize);
  send = stack + stsize - 16;
  send = (char *)((uintptr_t)send / 16 * 16);
  asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r"(send));
  func();
  asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  free(stack);
}
int dsu[1000002];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v); 
}
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  int c[n][m];
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      cin >> c[i][j];
    }
  }
  int q;
  cin >> q;
  int x[q], y[q];
  for(int i=0; i<q; i++) {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
    c[x[i]][y[i]] = 2 + i;
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      if(c[i][j] == 0) c[i][j] = MOD;
    }
  }
  int ans[q];
  for(int i=0; i<q; i++) ans[i] = 1;
  while(1) {
    int bruh[n][m];
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
        if(i > 0 && j > 0) {
          bruh[i][j] = min(c[i][j], bruh[i-1][j]);
          bruh[i][j] = max(bruh[i][j], min(c[i][j], bruh[i][j-1]));
        }
        else if(i > 0) {
          bruh[i][j] = min(c[i][j], bruh[i-1][j]);
        }
        else if(j > 0) {
          bruh[i][j] = min(c[i][j], bruh[i][j-1]);
        }
        else {
          bruh[i][j] = c[i][j];
        }
      }
    }
    int k = bruh[n-1][m-1];
    if(k < 2 || k == MOD) break;
    ans[k - 2] = 0;
    c[x[k - 2]][y[k - 2]] = MOD;
  }
  for(int i=0; i<q; i++) {
    cout << ans[i] << '\n';
  }
  

}
void uwu() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t; 
  for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
  #ifdef ONLINE_JUDGE
  uwu();
  #endif
  #ifndef ONLINE_JUDGE
  run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
  #endif
}
/*
g++ C.cpp -std=c++17 -O2 -o C
./C < input.txt
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 9 ms 860 KB Output is correct
6 Correct 10 ms 860 KB Output is correct
7 Correct 10 ms 860 KB Output is correct
8 Correct 10 ms 860 KB Output is correct
9 Correct 10 ms 860 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 9 ms 860 KB Output is correct
6 Correct 10 ms 860 KB Output is correct
7 Correct 10 ms 860 KB Output is correct
8 Correct 10 ms 860 KB Output is correct
9 Correct 10 ms 860 KB Output is correct
10 Correct 96 ms 3160 KB Output is correct
11 Correct 8 ms 4956 KB Output is correct
12 Correct 407 ms 26988 KB Output is correct
13 Correct 43 ms 16464 KB Output is correct
14 Execution timed out 5030 ms 42068 KB Time limit exceeded
15 Halted 0 ms 0 KB -