oj.uz

Submission #915123

# Submission time Handle Problem Language Result Execution time Memory
915123 2024-01-23T11:28:17 Z cig32 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 17744 KB 
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#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 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 10 ms 692 KB Output is correct
7 Correct 10 ms 604 KB Output is correct
8 Correct 11 ms 604 KB Output is correct
9 Correct 10 ms 604 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 10 ms 692 KB Output is correct
7 Correct 10 ms 604 KB Output is correct
8 Correct 11 ms 604 KB Output is correct
9 Correct 10 ms 604 KB Output is correct
10 Correct 97 ms 3220 KB Output is correct
11 Correct 7 ms 600 KB Output is correct
12 Correct 396 ms 12724 KB Output is correct
13 Correct 41 ms 8532 KB Output is correct
14 Execution timed out 5031 ms 17744 KB Time limit exceeded
15 Halted 0 ms 0 KB -