oj.uz

Submission #915121

# Submission time Handle Problem Language Result Execution time Memory
915121 2024-01-23T11:27:16 Z cig32 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 51908 KB 
#pragma GCC optimize("Ofast")
#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 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 6 ms 2652 KB Output is correct
6 Correct 6 ms 968 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 6 ms 2652 KB Output is correct
9 Correct 7 ms 860 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 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 6 ms 2652 KB Output is correct
6 Correct 6 ms 968 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 6 ms 2652 KB Output is correct
9 Correct 7 ms 860 KB Output is correct
10 Correct 51 ms 2140 KB Output is correct
11 Correct 6 ms 612 KB Output is correct
12 Correct 246 ms 25876 KB Output is correct
13 Correct 42 ms 17488 KB Output is correct
14 Correct 3578 ms 39420 KB Output is correct
15 Correct 3258 ms 43572 KB Output is correct
16 Correct 3883 ms 48084 KB Output is correct
17 Correct 4356 ms 50468 KB Output is correct
18 Correct 3826 ms 48708 KB Output is correct
19 Correct 4212 ms 51908 KB Output is correct
20 Execution timed out 5041 ms 50776 KB Time limit exceeded
21 Halted 0 ms 0 KB -