Submission #1205836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205836		ByeWorld	Inspections (NOI23_inspections)	C++20	100 / 100	605 ms	56712 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 2e5+10;
const int SQRT = 450;
const int INF = 2e18+10;
const int MOD = 998244353;
const int LOG = 20;
int sum(int a, int b){ return (a+MOD+b)%MOD; }
void chsum(int &a, int b){ a = (a+MOD+b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, m, q;
int ans[MAXN];
map<int,int> cnt;
set <ipii> ran;

void ins(int l, int r, int x){
	// cout << l << ' '<< r <<' ' << x << " x\n";
	auto it = ran.lower_bound(ipii(pii(l+1, -1),-1));
	if(it != ran.begin()) it--;
	vector<ipii> ADD;
	while(true){
		if(it==ran.end() || r < (*it).fi.fi) break;
		if((*it).fi.se < l){ it++; continue; }
		// cek perpot
		int X = (*it).fi.fi, Y = (*it).fi.se, TIM = (*it).se;
		int le = max(l, X), ri = min(r, Y);
		int delt = TIM + le-X, t = x+le-l; // le-ri, t...
		cnt[t-delt] += ri-le+1;

		// cout << t-delt << ' ' << ri-le+1 << " num\n";
		// delete
		auto it2 = it; it++;
		ran.erase(it2);
		if(X <= l-1) ADD.pb({pii(X, l-1), TIM});
		if(r+1 <= Y) ADD.pb({pii(r+1, Y), TIM + r+1-X});
	}
	// it = ran.begin();
	// while(it != ran.end()){
	// 	if(it==ran.end() || r < (*it).fi.fi || (*it).fi.se < l){
	// 		it++; continue;
	// 	}
	// 	// cek perpot
	// 	int X = (*it).fi.fi, Y = (*it).fi.se, TIM = (*it).se;
	// 	int le = max(l, X), ri = min(r, Y);
	// 	int delt = TIM + le-X, t = x+le-l; // le-ri, t...
	// 	cnt[t-delt] += ri-le+1;

	// 	// cout << t-delt << ' ' << ri-le+1 << " num\n";
	// 	// delete
	// 	auto it2 = it; it++;
	// 	ran.erase(it2);
	// 	if(X <= l-1) ADD.pb({pii(X, l-1), TIM});
	// 	if(r+1 <= Y) ADD.pb({pii(r+1, Y), TIM + r+1-X});
	// }

	for(auto in : ADD) ran.insert(in);
	ran.insert(ipii(pii(l, r), x));

	// for(auto [x, p] : ran) cout<<x.fi<<' '<<x.se<<' '<<p<<" pp\n";
	// 	cout <<"Xx\n";
}
// 1 2 3 3 4 5 2 3
// 1 2 3 4 5 2 3 1 2 3 4 5 2 3
// 1 2 4 5 1 2 3 4 5
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;

	int tim = 1;
	ran.insert({pii(n+1,n+1), -1});
	for(int i=1; i<=m; i++){
		int l, r; cin>>l>>r;
		ins(l, r, tim);
		tim += r-l+1;
		// for(int j=l; j<=r; j++){
		// 	++tim;
		// 	if(arr[j] != -1) cnt[tim-arr[j]]++;
		// 	arr[j] = tim;
		// }
	}
	vector<pii> CNT;
	for(auto [x, y] : cnt) CNT.pb({x,y}); 
	set <pii> s;
	int tot = 0;
	for(int j=CNT.size()-1; j>=0; j--){
		// cout << CNT[j].fi << ' ' << CNT[j].se << " xx\n";
		s.insert({CNT[j].fi, CNT[j].se+tot});
		tot += CNT[j].se;
	}
	s.insert({INF, 0});
	for(int i=1; i<=q; i++){
		int x; cin>>x; x++;
		ans[i] = (*s.lower_bound(pii(x, -1))).se;
	}
	for(int i=1; i<=q; i++) cout << ans[i] << " \n"[i==q];
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 23 / 23