提出 #68152943

---

ソースコード 拡げる

#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
//#undef ONLINE_JUDGE

namespace fastio
{
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        IN& operator>>(long double &a){getDouble(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        OUT& operator<<(long double a){putDouble(a);return *this;}
        ~OUT(){flush();}
    };
}
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;
#define cin fin
#define cout fout
#define int long long
void clear() {
}
int ans[500005];
mt19937 rnd(time(0));
struct ThisIsAValueSectionAddAndInsertZeroAndOnePointQueryValuesStructure {
	struct Info {
		int ls, rs, key, sz,vala, taga, mn;
	} t[2000001];
	int rt, tot;
	inline void push_up(int i) {
		if (!i) return;
		t[i].sz = t[t[i].ls].sz + t[t[i].rs].sz + 1;
		t[i].mn = min({t[i].vala, (t[i].ls ? t[t[i].ls].mn : 1ll << 61),(t[i].rs ? t[t[i].rs].mn : 1ll << 61)});
	}
	inline void settag(int i, int a) {
		if (!i) return;
		t[i].taga += a;
		t[i].vala += a;
		t[i].mn += a;
	}
	inline void push_down(int i) {
		if (!i) return;
		settag(t[i].ls, t[i].taga);
		settag(t[i].rs, t[i].taga);
		t[i].taga = 0;
	}
	inline void split(int u, int x, int &l, int &r) {
		if (!u) return l = r = 0, void();
		push_down(u);
		if (t[u].vala <= x) {
			l = u;
			split(t[u].rs, x, t[u].rs, r);
		} else {
			r = u;
			split(t[u].ls, x, l, t[u].ls);
		}
		push_up(u);
	}
	inline int merge(int x, int y) {
		push_down(x); push_down(y); push_up(x); push_up(y);
		if (!x || !y) return x | y;
		if (t[x].key < t[y].key) {
			t[x].rs = merge(t[x].rs, y);
			push_up(x);
			return x;
		} else {
			t[y].ls = merge(x, t[y].ls);
			push_up(y);
			return y;
		}
	}
	inline void output(int i, int fl) {
		if (!i) return;
		push_down(i);
		output(t[i].ls, fl);
		ans[i] = fl;
		output(t[i].rs, fl);
		push_up(i);
	}
	inline int make(int vala) {
		/*
		int ls, rs, key, sz, fa, vala, taga, valb, tagb, mn;
		*/
		t[++tot] = (Info){0, 0, rnd(), 1, vala, 0, vala};
		return tot;
	}
	inline int Merge(int les, int gre) {
		rt = 0;
		while (les && gre) {
			if (t[les].mn > t[gre].mn) swap(les, gre);
			int tmp;
			split(les, t[gre].mn, tmp, les);
			rt = merge(rt, tmp);
		}
		if (gre) rt = merge(rt, gre);
		if (les) rt = merge(rt, les);
		return rt;
	}
	inline void add(int x, int c) {
		settag(x, c);
	}
} t;
int n, l[500005], r[500005], x[500005], sz[500005], rt[500005];

void solve() {
	cin >> n;
	sz[1] = 1;
	sz[2] = 1;
	for (int i = 3; i <= n + 2; ++i) {
		cin >> l[i] >> r[i] >> x[i];
		l[i] += 1;
		r[i] += 1;
		sz[i] = sz[l[i]] + sz[r[i]];
		sz[i] = min(sz[i], 1ll << 61);
		rt[i] = t.make(x[i]);
	}
	for (int i = n + 2; i >= 3; --i) {
		int L, R;
		int mid = sz[l[i]];
		t.split(rt[i], mid, L, R);
		t.add(R, -mid);
		rt[l[i]] = t.Merge(rt[l[i]], L);
		rt[r[i]] = t.Merge(rt[r[i]], R);
	}
	t.output(rt[1], 0);
	t.output(rt[2], 1);
	for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
}


signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
//	cin >> tc;
	while (tc--) {
		clear();
		solve();
	}
	return 0;
}

提出情報

コンパイルエラー

Main.cpp: In member function ‘long long int ThisIsAValueSectionAddAndInsertZeroAndOnePointQueryValuesStructure::make(long long int)’:
Main.cpp:157:44: warning: narrowing conversion of ‘rnd.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()’ from ‘std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type’ {aka ‘long unsigned int’} to ‘long long int’ [-Wnarrowing]
  157 |                 t[++tot] = (Info){0, 0, rnd(), 1, vala, 0, vala};
      |                                         ~~~^~

ジャッジ結果