結果

問題 No.3614 Breaking door keys（LITTLE BREAK ver.）
コンテスト
ユーザー keisuke6
提出日時 2026-08-06 14:20:41
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 251 ms / 2,000 ms
+ 159µs
コード長 1,415 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,326 ms
コンパイル使用メモリ 224,488 KB
実行使用メモリ 18,032 KB
最終ジャッジ日時 2026-08-06 14:20:51
合計ジャッジ時間 9,386 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 3
小課題1 10 % AC * 7
小課題2 20 % AC * 7
小課題3 30 % AC * 7
小課題4 30 % AC * 14
小課題5 10 % AC * 38
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SEG{
private:
	int n;
	vector<int> node;
public:
	SEG(int N){
		n = 1;
		while(n < N) n *= 2;
		node.resize(2*n+1);
	}
	void add(int i, int x){
		for(i++;i<=n;i+=i&-i) node[i] += x;
	}
	int f_(int i){
		int ans = 0;
		for(;i>0;i-=i&-i) ans += node[i];
		return ans;
	}
	int f(int l, int r){
		return f_(r)-f_(l);
	}
};
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	srand((unsigned)time(NULL));
	int N,Q;
	cin>>N>>Q;
	vector<pair<int,int>> I(N);
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		I[i] = {a,i};
	}
	sort(I.begin(),I.end());
	vector<int> L(Q), R(Q), K(Q), AC(Q), WA(Q);
	for(int i=0;i<Q;i++){
		cin>>L[i]>>R[i]>>K[i];
		L[i]--;
		AC[i] = -1; // -1 個選んでいる状態では <= K
		WA[i] = N+1; // N+1 個は選べないので
	}
	int pb = 18;
	vector<int> Ans(Q);
	while(pb--){
		SEG segk(N), segc(N); // kosuu cost
		vector<vector<int>> Ls(N+1);
		for(int i=0;i<Q;i++) Ls[(AC[i]+WA[i])/2].push_back(i);
		for(int i=0;i<=N;i++){
			for(int pl:Ls[i]){
				int k = segk.f(L[pl],R[pl]);
				if(k <= K[pl]){
					AC[pl] = i;
					Ans[pl] = segc.f(L[pl],R[pl]);
				}
				else WA[pl] = i;
			}
			if(i == N) continue;
			auto [c,p] = I[i];
			segk.add(p,1);
			segc.add(p,c);
			//for(int j=0;j<N;j++) cout<<segc.f(j,j+1)<<' ';
			//cout<<endl;
		}
	}
	for(int x:Ans) cout<<x<<endl;
}
0