結果
問題 | No.2786 RMQ on Grid Path |
ユーザー |
![]() |
提出日時 | 2024-06-14 22:07:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,714 ms / 6,000 ms |
コード長 | 1,295 bytes |
コンパイル時間 | 4,476 ms |
コンパイル使用メモリ | 258,008 KB |
最終ジャッジ日時 | 2025-02-21 22:02:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int main(){ int h,w; cin>>h>>w; vector a(h,vector(w,0)); vector<vector<pair<int,int>>> pos(h*w+1); rep(i,h){ rep(j,w){ cin>>a[i][j]; pos[a[i][j]].push_back({i,j}); } } int q; cin>>q; vector<int> x(q),y(q),z(q),ww(q); vector<int> ok(q,h*w),ng(q,0); rep(i,q){ cin>>x[i]>>y[i]>>z[i]>>ww[i]; x[i]--;y[i]--,z[i]--,ww[i]--; } vector<int> dx = {1,-1,0,0},dy = {0,0,1,-1}; rep(_,20){ vector<vector<int>> mids(h*w+1); rep(i,q){ if(ok[i]-ng[i]>1){ mids[(ok[i]+ng[i])/2].push_back(i); } } dsu D(h*w); rep(i,h*w+1){ rep(j,pos[i].size()){ int x = pos[i][j].first,y = pos[i][j].second; rep(k,4){ int nx = x+dx[k],ny = y+dy[k]; if(nx<0||nx>=h||ny<0||ny>=w) continue; if(a[nx][ny]>a[x][y]) continue; D.merge(x*w+y,nx*w+ny); } } rep(j,mids[i].size()){ if(D.same(x[mids[i][j]]*w+y[mids[i][j]],z[mids[i][j]]*w+ww[mids[i][j]])){ ok[mids[i][j]] = i; } else ng[mids[i][j]] = i; } } } rep(i,q){ cout<<ok[i]<<endl; } return 0; }