結果

問題 No.1338 Giant Class
ユーザー kanra824
提出日時 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,
      |       ^~

ソースコード

diff #
プレゼンテーションモードにする

#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 xg(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0