oj.uz

Submission #543618

# Submission time Handle Problem Language Result Execution time Memory
543618 2022-03-31T02:42:00 Z amunduzbaev New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 22004 KB 
#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] += t * (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;
		if(i <= m) return (f[x][0] ? get(i, lx, m, f[x][0]) : 0) + res;
		else return (f[x][1] ? get(i, m+1, rx, f[x][1]) : 0) + 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; break; }
		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;
		vector<int> d(k, -1);
		
		for(int i=0;i<n;i++){
			if(a[i] <= y && y <= b[i]){
				if(d[t[i]] == -1 || d[t[i]] > abs(l - x[i])){
					d[t[i]] = abs(l - x[i]);
				}
			}
		}
		
		bool ok = 1;
		int res = 0;
		for(int i=0;i<k;i++){
			if(d[i] == -1) ok = 0;
			else res += d[i];
		}
		
		if(ok) cout<<res<<"\n";
		else cout<<-1<<"\n";
		//~ if(is){
			//~ cout<<tree.get(l)<<"\n";
		//~ } else {
			//~ cout<<-1<<"\n";
		//~ }
	}
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:64:7: warning: variable 'is' set but not used [-Wunused-but-set-variable]
   64 |  bool is = 1;
      |       ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Incorrect 4 ms 7300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Incorrect 4 ms 7300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 22004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 20580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Incorrect 4 ms 7300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Incorrect 4 ms 7300 KB Output isn't correct
5 Halted 0 ms 0 KB -