Submission #543616

#	Time	Username	Problem	Language	Result	Execution time	Memory
543616		amunduzbaev	New Home (APIO18_new_home)	C++17	0 / 100	1364 ms	328024 KiB

new_home

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int M = 15e6 + 5;
const int MX = 1e8 + 5;

struct ST{
	int tree[M], D[M], f[M][2];
	int last;
	ST(){
		last = 0;
	}
	
	void make(int x){
		if(!f[x][0]) f[x][0] = ++last;
		if(!f[x][1]) f[x][1] = ++last;
	}
	
	void add(int l, int r, int t = 1, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += t * (lx - l);
			D[x] += t; return;
		} int m = (lx + rx) >> 1;
		make(x);
		add(l, r, t, lx, m, f[x][0]), add(l, r, t, m+1, rx, f[x][1]);
	}
	
	void rev(int l, int r, int t = 1, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += (r - lx);
			D[x] -= t; return;
		} int m = (lx + rx) >> 1;
		make(x);
		rev(l, r, t, lx, m, f[x][0]), rev(l, r, t, m+1, rx, f[x][1]);
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = tree[x] + (i - lx) * D[x];
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		make(x);
		if(i <= m) return get(i, lx, m, f[x][0]) + res;
		else return get(i, m+1, rx, f[x][1]) + res;
	}
}tree;

const int N = 3e5 + 5;
int x[N], t[N], a[N], b[N], l[N], y[N];
vector<int> stor[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		stor[--t[i]].push_back(i);
	}
	
	bool is = 1;
	for(int i=0;i<k;i++){
		if(stor[i].empty()) is = 0;
		sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
			return (x[i] < x[j]);
		});
		for(int j=1;j<(int)stor[i].size();j++){
			int l = x[stor[i][j-1]], r = x[stor[i][j]];
			if(l == r) continue;
			int m = (l + r) >> 1;
			tree.add(0, m);
			tree.rev(m + 1, r);
		}
		
		tree.rev(0, x[stor[i][0]]);
		tree.add(x[stor[i].back()], MX);
	}
	
	while(q--){
		int l, y;
		cin>>l>>y;
		if(is){
			cout<<tree.get(l)<<"\n";
		} else {
			cout<<-1<<"\n";
		}
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20