結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | lumc_ |
提出日時 | 2018-01-01 18:36:25 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 464 ms / 2,000 ms |
コード長 | 4,153 bytes |
コンパイル時間 | 1,041 ms |
コンパイル使用メモリ | 105,208 KB |
実行使用メモリ | 9,696 KB |
最終ジャッジ日時 | 2024-10-02 09:25:27 |
合計ジャッジ時間 | 8,339 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 315 ms
6,820 KB |
testcase_01 | AC | 462 ms
8,548 KB |
testcase_02 | AC | 460 ms
8,984 KB |
testcase_03 | AC | 456 ms
8,512 KB |
testcase_04 | AC | 459 ms
9,224 KB |
testcase_05 | AC | 464 ms
8,472 KB |
testcase_06 | AC | 178 ms
8,484 KB |
testcase_07 | AC | 101 ms
8,388 KB |
testcase_08 | AC | 341 ms
8,716 KB |
testcase_09 | AC | 398 ms
8,108 KB |
testcase_10 | AC | 280 ms
8,484 KB |
testcase_11 | AC | 251 ms
8,396 KB |
testcase_12 | AC | 314 ms
9,696 KB |
testcase_13 | AC | 287 ms
7,712 KB |
testcase_14 | AC | 128 ms
6,820 KB |
testcase_15 | AC | 248 ms
7,856 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 3 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 2 ms
6,820 KB |
ソースコード
// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15 const bool DEBUG = 1; #include <iostream> #include <vector> #include <array> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <tuple> #include <algorithm> #include <cmath> #include <cstring> #include <complex> #include <random> #include <iomanip> #include <cassert> #include <functional> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef tuple<ll, ll> P; typedef tuple<ll, ll, ll> P3; typedef vector<int> VI; typedef vector<ll> VL; typedef vector<P> VP; typedef vector<string> VS; #define omajinai ios::sync_with_stdio(false);cin.tie(0) #define FOR(i,a,b) for(int i=int(a);i<int(b);++i) #define REP(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i) #define RREP(i,n) RFOR(i,0,n) #define ALL(a) (a).begin(),(a).end() #define UNIQUE(a) (a).erase(unique(ALL(a)),(a).end()) #define EACH(i,c) REP(i,(c).size()) #define REACH(i,c) RREP(i,(c).size()) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define SORT(c) sort(ALL(c)) #define BR cout<<"\n" #define dump(x) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<#x<<"="<<(x)<<"\n" #define dump2(x,y) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<#x<<"="<<(x)\ <<" , "<<#y<<"="<<(y)<<"\n" #define dump3(x,y,z) if(DEBUG)cerr<<"["<<__LINE__<<"] "<<#x<<"="<<(x)\ <<" , "<<#y<<"="<<(y)\ <<" , "<<#z<<"="<<(z)<<"\n" #define SAY(x) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<(x)<<"\n" #define YES(x) cout<<((x)?"YES":"NO")<<"\n" #define Yes(x) cout<<((x)?"Yes":"No")<<"\n" #define yes(x) cout<<((x)?"yes":"no")<<"\n" inline int omajinai_int_in(){omajinai;int n;cin>>n;return n;} inline ll omajinai_ll_in(){omajinai;ll n;cin>>n;return n;} inline string omajinai_string_in(){omajinai;string n;cin>>n;return n;} inline int int_in(){int n;cin>>n;return n;} inline ll ll_in(){ll n;cin>>n;return n;} inline string string_in(){string n;cin>>n;return n;} #define oini omajinai_int_in() #define oinl omajinai_ll_in() #define oins omajinai_string_in() #define ini int_in() #define inl ll_in() #define ins string_in() #define isInside(x,y) (0<=(x)&&(x)<w&&0<=(y)&&(y)<h) #define fi(x) (get<0>(x)) #define se(x) (get<1>(x)) #define th(x) (get<2>(x)) #define fo(x) (get<3>(x)) constexpr int INF = 1e9+1; constexpr ll LINF = 1e18+1; constexpr int MOD = 1e9+7; template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; EACH(i, v) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]"; return o; } template <typename T> function<T(T,T)> constexpr mmin(){ return [](T x, T y){return x<y?x:y;}; } template <typename T> function<T(T,T)> constexpr mmax(){ return [](T x, T y){return x>y?x:y;}; } template <typename T> function<T(T,T)> constexpr madd(){ return [](T x, T y){return x+y;}; } template <typename T> function<T(T,T)> constexpr modadd(){ return [](T x, T y){return ((x+y)%MOD+MOD)%MOD;}; } const int N = 1e5-1; int n=ini; struct LazySegTree { ll data[N*4]; ll lazy[N*4]; int m; void init(int n) { m = 1; while(m<n) m<<=1; REP(i, m*2-1) { data[i] = -LINF; lazy[i] = 0; } } void eval(int k, int l, int r) { if(!lazy[k]) return; data[k] += lazy[k] / (r-l); if(r-l>1) { lazy[k*2+1] += lazy[k]/2; lazy[k*2+2] += lazy[k]/2; } lazy[k] = 0; } void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if(r<0) r = m; eval(k, l, r); if(b<=l||r<=a) return; if(a<=l&&r<=b) { lazy[k] += x * (r-l); eval(k, l, r); return; } add(a, b, x, k*2+1, l, (l+r)/2); add(a, b, x, k*2+2, (l+r)/2, r); data[k] = max(data[k*2+1], data[k*2+2]); } ll getMax(int a, int b, int k = 0, int l = 0, int r = -1) { if(r<0) r = m; eval(k, l, r); if(b<=l||r<=a) return -LINF; if(a<=l&&r<=b) return data[k]; return max( getMax(a, b, k*2+1, l, (l+r)/2), getMax(a, b, k*2+2, (l+r)/2, r) ); } }; LazySegTree tree; int main() { //#####// tree.init(n-1); REP(i, n-1) { tree.add(i, i+1, LINF + ini + (n - i - 1) * 3); } int q = ini; REP(i, q) { int a = ini-1, b = ini-1, x = ini; tree.add(a, b+1, x); cout << tree.getMax(0, n-1) << endl; } } //