結果
問題 | No.1338 Giant Class |
ユーザー |
|
提出日時 | 2021-01-16 05:06:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 2,530 bytes |
コンパイル時間 | 2,066 ms |
コンパイル使用メモリ | 204,060 KB |
最終ジャッジ日時 | 2025-01-17 21:16:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
/*** author: otera**/#include<bits/stdc++.h>using namespace std;#define int long longtypedef long long ll;typedef long double ld;const int inf=1e9+7;const ll INF=1LL<<60;#define rep(i, n) for(int i = 0; i < n; ++ i)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)typedef pair<int, int> P;typedef pair<ll, ll> LP;#define fr first#define sc second#define all(c) c.begin(),c.end()template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }template<typename T>struct SegmentTree{private:int n;T E;vector<T> node;inline void updatef(T& x,T& y){//x = y;// x += y;//x = max(x,y);x = min(x,y);}inline T queryf(T& x,T& y){//return min(x,y);return x+y;//return max(x,y);}public:SegmentTree(int sz,T E_):E(E_){n=1;while(n<sz)n<<=1;node.resize(2*n-1,E);}SegmentTree(vector<T>& A,T E_):E(E_){int sz=A.size();n=1;while(n<sz)n<<=1;node.resize(2*n-1,E);rep(i,sz)node[i+n-1]=A[i];for(int i=n-2;i>=0;--i){node[i]=queryf(node[2*i+1], node[2*i+2]);}}void update(int k,T x){k+=n-1;updatef(node[k],x);while(k>0){k=(k-1)/2;node[k]=queryf(node[2*k+1], node[2*k+2]);}}//[a,b)での値を返すT get(int a,int b,int k=0,int l=0,int r=-1){if(r<0)r=n;if(r<=a||b<=l)return E;if(a<=l&&r<=b)return node[k];T xl=get(a,b,2*k+1,l,(l+r)/2);T xr=get(a,b,2*k+2,(l+r)/2,r);return queryf(xl, xr);}};void solve() {int h, w; cin >> h >> w;int q; cin >> q;vector<int> y(q), x(q);rep(i, q) {cin >> y[i] >> x[i];-- y[i], -- x[i];}auto comx = x;sort(all(comx));comx.erase(unique(all(comx)), comx.end());int sz = (int)comx.size();ll offset = (w - sz) * h;vector<int> vec(sz, h);SegmentTree<int> seg(vec, 0);rep(i, q) {x[i] = lower_bound(all(comx), x[i]) - comx.begin();seg.update(x[i], y[i]);cout << offset + seg.get(0, sz) << "\n";}}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(20);//int t; cin >> t; rep(i, t)solve();solve();return 0;}