結果
問題 | No.1234 典型RMQ |
ユーザー |
![]() |
提出日時 | 2020-09-18 22:25:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 6,913 bytes |
コンパイル時間 | 1,926 ms |
コンパイル使用メモリ | 206,476 KB |
最終ジャッジ日時 | 2025-01-14 17:26:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘void scan(char*)’: main.cpp:57:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 57 | void scan(char a[]) { scanf("%s", a); } | ~~~~~^~~~~~~~~
ソースコード
/** * author: nok0 * created: 2020.09.18 22:22:59 **/ #ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> using namespace std; #pragma region Macros #define ll long long #define ld long double #define FOR(i,l,r) for(int i=(l);i<(r);++i) #define REP(i,n) FOR(i,0,n) #define REPS(i,n) FOR(i,1,n+1) #define RFOR(i,l,r) for(int i=(l);i>=(r);--i) #define RREP(i,n) RFOR(i,n-1,0) #define RREPS(i,n) RFOR(i,n,1) #define pb push_back #define eb emplace_back #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() template<class T = int> using V = vector<T>; template<class T = int> using VV = V<V<T>>; using pii = pair<int, int>; using pll = pair<ll, ll>; #define VEC(type, name, size)\ V<type> name(size);\ IN(name) #define VVEC(type, name, h, w)\ VV<type> name(h, V<type>(w));\ IN(name) #define INT(...)\ int __VA_ARGS__;\ IN(__VA_ARGS__) #define LL(...)\ ll __VA_ARGS__;\ IN(__VA_ARGS__) #define STR(...)\ string __VA_ARGS__;\ IN(__VA_ARGS__) #define CHAR(...)\ char __VA_ARGS__;\ IN(__VA_ARGS__) #define DOUBLE(...)\ DOUBLE __VA_ARGS__;\ IN(__VA_ARGS__) #define LD(...)\ LD __VA_ARGS__;\ IN(__VA_ARGS__) void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(double &a) { cin >> a; } void scan(long double &a) { cin >> a; } void scan(char a[]) { scanf("%s", a); } void scan(string &a) { cin >> a; } template <class T> void scan(V<T> &); template <class T, class L> void scan(pair<T, L> &); template <class T> void scan(V<T> &a) { for(auto &i : a) scan(i); } template <class T, class L> void scan(pair<T, L> &p){ scan(p.first); scan(p.second); } template <class T> void scan(T &a) { cin >> a; } void IN() {} template <class Head, class... Tail> void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); } template <class T> inline void print(T x){ cout << x << '\n';} template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p){ is >> p.first >> p.second; return is; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){ os << p.first << " " << p.second; return os; } template <class T> ostream &operator<<(ostream &os, const V<T> &v){ REP(i, SZ(v)){ if(i) os << " "; os << v[i]; } return os; } //debug template <typename T> void view(const V<T> &v){ cerr << "{ "; for(const auto &e : v){ cerr << e << ", "; } cerr << "\b\b }"; } template <typename T> void view(const VV<T> &vv){ cerr << "{\n"; for(const auto &v : vv){ cerr << "\t"; view(v); cerr << "\n"; } cerr << "}"; } template <typename T, typename U> void view(const V<pair<T, U>> &v){ cerr << "{\n"; for(const auto &c : v) cerr << "\t(" << c.first << ", " << c.second << ")\n"; cerr << "}"; } template <typename T, typename U> void view(const map<T, U> &m){ cerr << "{\n"; for(auto &t : m) cerr << "\t[" << t.first << "] : " << t.second << "\n"; cerr << "}"; } template <typename T, typename U> void view(const pair<T, U> &p){ cerr << "(" << p.first << ", " << p.second << ")";} template <typename T> void view(const set<T> &s) { cerr << "{ "; for(auto &t : s) { view(t); cerr << ", "; } cerr << "\b\b }"; } template <typename T> void view(T e) { cerr << e;} #ifdef LOCAL void debug_out() {} template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { view(H); cerr << ", "; debug_out(T...); } #define debug(...) \ do{ \ cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \ debug_out(__VA_ARGS__); \ cerr << "\b\b]\n"; \ } while(0) #else #define debug(...) (void(0)) #endif template <class T> V<T> press(V<T> &x){ V<T> res = x; sort(all(res)); res.erase(unique(all(res)), res.end()); REP(i, SZ(x)){ x[i] = lower_bound(all(res), x[i]) - res.begin(); } return res; } template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; } template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; } inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';} inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';} inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}} template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}} template<class T> T divup(T x, T y) {return (x+(y-1))/y;} template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; } struct iofast{iofast(){ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15);}}iofast_; const int inf = 1e9; const ll INF = 1e18; #pragma endregion template<typename T> class segtree { private: int n,sz,h; vector<pair<T, int> > node; vector<T> lazy; void eval(int k) { if(lazy[k]){ node[k].first += lazy[k]; if(k < n) { lazy[k*2] += lazy[k], lazy[k*2+1] += lazy[k]; } lazy[k] = 0; } } public: segtree(const vector<T>& v) : sz((int)v.size()), h(0) { n = 1; while(n < sz) n *= 2, h++; node.resize(2*n, pair<T, int>(numeric_limits<T>::max(), sz)); lazy.resize(2*n, 0); for(int i = 0; i < sz; i++){ node[i+n] = make_pair(v[i], i); } for(int i = n-1; i >= 1; i--){ node[i] = min(node[2*i], node[2*i+1]); } } void range(int a, int b, T x, int k=1, int l=0, int r=-1){ if(r < 0) r = n; eval(k); if(b <= l || r <= a){ return; } if(a <= l && r <= b){ lazy[k] += x; eval(k); }else{ range(a, b, x, 2*k, l, (l+r)/2); range(a, b, x, 2*k+1, (l+r)/2, r); node[k] = min(node[2*k], node[2*k+1]); } } pair<T, int> query(int a, int b) { a += n, b += n - 1; for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i); b++; pair<T, int> res1 = make_pair(numeric_limits<T>::max(), sz); pair<T, int> res2 = make_pair(numeric_limits<T>::max(), sz); while(a < b) { if(a & 1) eval(a), res1 = min(res1, node[a++]); if(b & 1) eval(--b), res2 = min(res2, node[b]); a >>= 1, b >>= 1; } return min(res1, res2); } void print() { for(int i = 0; i < sz; i++){ pair<T,int> p; p = query(i,i+1); cout << "st[" << i << "]: " << p.first << " " << p.second << endl; } } }; int main(){ INT(n); VEC(ll, a, n); segtree<ll> ST(a); INT(q); while(q--){ INT(type, l, r, c); l--; if(type == 1){ ST.range(l, r, c); } else print(ST.query(l, r).first); } }