結果
問題 | No.1338 Giant Class |
ユーザー |
|
提出日時 | 2021-01-15 21:53:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 357 ms / 2,000 ms |
コード長 | 6,760 bytes |
コンパイル時間 | 4,364 ms |
コンパイル使用メモリ | 213,492 KB |
最終ジャッジ日時 | 2025-01-17 19:15:18 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:283:7: warning: narrowing conversion of ‘id’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing] 283 | id, | ^~
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i, n) for(int i=0; i<(n); ++i)#define RREP(i, n) for(int i=(n);i>=0;--i)#define FOR(i, a, n) for (int i=(a); i<(n); ++i)#define RFOR(i, a, b) for(int i=(a);i>=(b);--i)#define SZ(x) ((int)(x).size())#define ALL(x) (x).begin(),(x).end()#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;template<class T>ostream &operator<<(ostream &os, const vector<T> &v) {REP(i, SZ(v)) {if (i) os << " ";os << v[i];}return os;}template <class T>void debug(const vector<T> &v) {cout << "[";REP(i, SZ(v)) {if(i) cout << ", ";cout << v[i];}cout << "]" << endl;}template<class T, class U>ostream &operator<<(ostream &os, const pair<T, U> &p) {return os << p.first << " " << p.second;}template <class T, class U>void debug(const pair<T, U> &p) {cout << "(" << p.first << " " << p.second << ")" << endl;}template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template<class T>bool chmin(T &a, const T &b) {if (b < a) {a = b;return true;}return false;}using ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;using vvi = vector<vi>;using vvll = vector<vll>;const ll MOD = 1e9 + 7;const ll MOD998 = 998244353;const int INF = INT_MAX;const ll LINF = LLONG_MAX;const int inf = INT_MIN;const ll linf = LLONG_MIN;const ld eps = 1e-9;template<int m>struct mint {int x;mint(ll x = 0) : x(((x % m) + m) % m) {}mint operator-() const { return x ? m - x : 0; }mint &operator+=(mint r) {if ((x += r.x) >= m) x -= m;return *this;}mint &operator-=(mint r) {if ((x -= r.x) < 0) x += m;return *this;}mint &operator*=(mint r) {x = ((ll) x * r.x) % m;return *this;}mint inv() const { return pow(m - 2); }mint &operator/=(mint r) { return *this *= r.inv(); }friend mint operator+(mint l, mint r) { return l += r; }friend mint operator-(mint l, mint r) { return l -= r; }friend mint operator*(mint l, mint r) { return l *= r; }friend mint operator/(mint l, mint r) { return l /= r; }mint pow(ll n) const {mint ret = 1, tmp = *this;while (n) {if (n & 1) ret *= tmp;tmp *= tmp, n >>= 1;}return ret;}friend bool operator==(mint l, mint r) { return l.x == r.x; }friend bool operator!=(mint l, mint r) { return l.x != r.x; }friend ostream &operator<<(ostream &os, mint a) {return os << a.x;}friend istream &operator>>(istream &is, mint &a) {ll x;is >> x;a = x;return is;}};using Int = mint<MOD>;/*** @brief セグメント木* @author habara-k, Md* @date 2020/06/17*/template<typename M>struct SegmentTree {/*** @brief コンストラクタ. O(n)* @param[in] n セグ木のサイズ.* @param[in] f モノイドの演算(query).* @param[in] g モノイドの演算(update).* @param[in] e モノイドの単位元.* @details 使い方* e.g. Update and Range Minimum* SegmentTree<int> segt(* n,* [](int a,int b){ return min(a+b); },* [](int a, int b){ return b; },* INF);* // 全て単位元で初期化される.*/SegmentTree(int n,const function<M(M, M)> &f,const function<M(M, M)> &g,const M &e) : n(n), f(f), g(g), e(e) {sz = 1;while (sz < n) sz <<= 1;data.assign(2 * sz, e);}/*** @brief 全体に初期値を入れる. O(n)* @param[in] v 要素モノイドのvector. 初期化する.* @details 使い方* segt.build(vector<int>(n, 0));*/void build(const vector<M> &v) {assert(v.size() <= n);for (int i = 0; i < v.size(); ++i) {data[i + sz] = v[i];}for (int i = sz - 1; i > 0; --i) {data[i] = f(data[2 * i], data[2 * i + 1]);}}/*** @brief 指定した位置に更新クエリを実行する O(log n)* @param[in] idx 位置idxに作用させる* @param[in] val 値xをg(data[idx+sz], val)で更新する*/void update(int idx, M val) {idx += sz;data[idx] = g(data[idx], val);while (idx >>= 1) {data[idx] = f(data[2 * idx], data[2 * idx + 1]);}}/*** @brief 指定した区間に取得クエリを実行する. O(log n)* @param[in] l, r 区間[l, r) を取得する.* @return 取得した値.* @details 使い方* e.g. Range Minimum* int l, r; // 区間[l, r) のminを取得したい.* cout << segt.query(l, r) << endl;*/M query(int a, int b) const {return query(a, b, 1, 0, sz);}/*** @brief 指定したindexの要素を取得. O(1)* @param[in] i 取得したい要素のindex* @return 取得した値.*/M operator[](int k) const {return data[k + sz];}/*** @brief vector みたいに出力.*/friend ostream &operator<<(ostream &os, SegmentTree &s) {os << "[";for (int i = 0; i < s.n; ++i) {if (i) os << " ";os << s[i];}return os << "]";}private:int n, sz;vector<M> data;const function<M(M, M)> f, g;const M e;M query(int a, int b, int k, int l, int r) const {if (r <= a || b <= l) {return e;} else if (a <= l && r <= b) {return data[k];} else {return f(query(a, b, 2 * k, l, (l + r) / 2),query(a, b, 2 * k + 1, (l + r) / 2, r));}}};int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(10);ll h, w, q; cin >> h >> w >> q;vector<ll> y(q), x(q);set<int> zatu;REP(i, q) {cin >> y[i] >> x[i];zatu.insert(x[i]);}ll id = 0;map<int, int> mp;for(auto &e: zatu) {mp[e] = id++;}ll add = h * (w - id);SegmentTree<ll> st = {id,[](ll a, ll b) {return a + b;},[](ll a, ll b) {return b;},0};vll init(id);REP(i, id) {init[i] = h;}st.build(init);REP(i, q) {ll val = st.query(mp[x[i]], mp[x[i]]+1);st.update(mp[x[i]], min(val, y[i]-1));cout << st.query(0, id) + add << endl;}return 0;}