oj.uz

Submission #915128

# Submission time Handle Problem Language Result Execution time Memory
915128 2024-01-23T11:31:17 Z cig32 Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 41580 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() { uwu();
}
/*
g++ C.cpp -std=c++17 -O2 -o C
./C < input.txt
*/

Compilation message

furniture.cpp:25:13: warning: 'void run_with_stack_size(void (*)(), size_t)' defined but not used [-Wunused-function]
   25 | static void run_with_stack_size(void (*func)(void), size_t stsize) {
      |             ^~~~~~~~~~~~~~~~~~~

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 600 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 848 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 6 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 600 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 848 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 6 ms 860 KB Output is correct
10 Correct 55 ms 1876 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 257 ms 22440 KB Output is correct
13 Correct 44 ms 14160 KB Output is correct
14 Correct 4944 ms 34852 KB Output is correct
15 Correct 3744 ms 35024 KB Output is correct
16 Correct 4218 ms 38152 KB Output is correct
17 Correct 4478 ms 40120 KB Output is correct
18 Correct 4030 ms 39164 KB Output is correct
19 Correct 4846 ms 41580 KB Output is correct
20 Execution timed out 5019 ms 39540 KB Time limit exceeded
21 Halted 0 ms 0 KB -