#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;
| ^~
# |
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 |
- |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5062 ms |
22004 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5073 ms |
20580 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
- |
# |
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 |
- |