結果

問題 No.3314 Library Rearrangement
コンテスト
ユーザー Moqing Zhang
提出日時 2026-10-25 21:33:24
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,094 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,941 ms
コンパイル使用メモリ 360,548 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2026-10-25 21:33:41
合計ジャッジ時間 15,406 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , k , q , a[50005] , cnt[50005] , ans[50005];
struct p
{
	int l , r , x;
}upd[10005] , qry[50005];
struct node
{
	int l , r , tag;
};
struct xds
{
	node tree[200005];
	inline void build(int p , int l , int r)
	{
		tree[p].l = l;
		tree[p].r = r;
		if(tree[p].l == tree[p].r)
		{
			tree[p].tag = 0;
			return;
		}
		int mid = (l + r) / 2;
		build(p * 2 , l , mid);
		build(p * 2 + 1 , mid + 1 , r);
		tree[p].tag = tree[p * 2].tag + tree[p * 2 + 1].tag;
		return;
	}
	inline void upd(int p , int l , int k)
	{
		if(tree[p].l == tree[p].r)
		{
			tree[p].tag += k;
			return;
		}
		if(tree[p * 2].r >= l)
		{
			upd(p * 2 , l , k);
		}
		else
		{
			upd(p * 2 + 1 , l , k);
		}
		tree[p].tag = tree[p * 2].tag + tree[p * 2 + 1].tag;
		return;
	}
	inline int query(int p , int l , int r)
	{
		if(l <= tree[p].l && tree[p].r <= r)
		{
			return tree[p].tag;
		}
		int cnt = 0;
		if(tree[p * 2].r >= l)
		{
			cnt += query(p * 2 , l , r);
		}
		if(tree[p * 2 + 1].l <= r)
		{
			cnt += query(p * 2 + 1 , l , r);
		}
		return cnt;
	}
}xds;
signed main()
{
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> q;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i];
	}
	for(int i = 1 ; i <= k ; i++)
	{
		cin >> upd[i].l >> upd[i].r >> upd[i].x;
	}
	xds.build(1 , 1 , n);
	for(int i = 1 ; i <= n ; i++)
	{
		xds.upd(1 , i , a[i]);
	}
	for(int i = 1 ; i <= q ; i++)
	{
		cin >> qry[i].l >> qry[i].r >> qry[i].x;
		cnt[i] = xds.query(1 , qry[i].l , qry[i].r);
		ans[i] = -1;
		if(cnt[i] >= qry[i].x)
		{
			ans[i] = 0;
		}
	}
	for(int i = 1 ; i <= k ; i++)
	{
		xds.build(1 , 1 , n);
		for(int j = upd[i].l ; j <= upd[i].r ; j++)
		{
			if(a[j] < upd[i].x)
			{
				xds.upd(1 , j , upd[i].x - a[j]);
				a[j] = upd[i].x;
			}
		}
		for(int j = 1 ; j <= q ; j++)
		{
			if(ans[j] == -1)
			{
				cnt[j] += xds.query(1 , qry[j].l , qry[j].r);
				if(cnt[j] >= qry[j].x)
				{
					ans[j] = i;
				}
			}
		}
	}
	for(int i = 1 ; i <= q ; i++)
	{
		cout << ans[i] << '\n';
	}
	return 0;
}
0