結果

問題 No.631 Noelちゃんと電車旅行
ユーザー lumc_lumc_
提出日時 2018-01-01 18:36:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 4,153 bytes
コンパイル時間 1,013 ms
コンパイル使用メモリ 104,896 KB
実行使用メモリ 9,044 KB
最終ジャッジ日時 2024-04-10 07:40:37
合計ジャッジ時間 8,357 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 321 ms
6,812 KB
testcase_01 AC 455 ms
8,616 KB
testcase_02 AC 455 ms
8,540 KB
testcase_03 AC 450 ms
8,700 KB
testcase_04 AC 454 ms
8,516 KB
testcase_05 AC 459 ms
8,644 KB
testcase_06 AC 176 ms
8,396 KB
testcase_07 AC 102 ms
8,388 KB
testcase_08 AC 342 ms
9,044 KB
testcase_09 AC 390 ms
8,468 KB
testcase_10 AC 273 ms
8,692 KB
testcase_11 AC 246 ms
7,700 KB
testcase_12 AC 314 ms
7,552 KB
testcase_13 AC 291 ms
5,376 KB
testcase_14 AC 128 ms
5,376 KB
testcase_15 AC 246 ms
6,940 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
	}
}

//
0