#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 300001;
template<int SZ> struct seg {
multiset<int> seg[2*SZ];
void trans(multiset<int>& m, int x, int d) {
if (d > 0) m.insert(x);
else m.erase(m.find(x));
}
void upd(int l, int r, int x, int d) {
for (l += SZ, r += SZ+1;l<r; l /= 2, r /= 2) {
if (l&1) trans(seg[l++],x,d);
if (r&1) trans(seg[--r],x,d);
}
}
int query(int x) {
int ans = -MOD;
for (x += SZ; x; x /= 2) if (sz(seg[x])) ans = max(ans,*seg[x].rbegin());
return ans;
}
};
seg<1<<20> S[2];
int n,k,q,ans[MX];
map<int,int> m;
multiset<int> tmp[MX];
vector<array<int,4>> ev;
void tri (int l, int r, int t) {
if (abs(t) == 1) {
m[l] = m[r] = 0;
if (l != -MOD && r != MOD) m[(l+r+1)/2] = 0;
//cout << "AA\n";
} else {
//cout << "BB\n";
if (l == -MOD) {
if (r == MOD) return;
S[1].upd(0,m[r]-1,r,t);
} else {
// cout << "AH " << l << " " << m[l] << " " << sz(m)-1 << "\n";
if (r == MOD) S[0].upd(m[l],sz(m)-1,-l,t);
else {
S[0].upd(m[l],m[(l+r+1)/2]-1,-l,t);
S[1].upd(m[(l+r+1)/2],m[r]-1,r,t);
}
}
}
}
int ok = 0;
void ad(int x, int y, int t) { // team, position
// cout << "HA " << x << " " << y << " " << t << "\n";
if (t > 0) {
if (sz(tmp[x]) == 2) ok ++;
tmp[x].insert(y);
}
auto it = tmp[x].find(y);
tri(*prev(it),*it,t);
tri(*it,*next(it),t);
tri(*prev(it),*next(it),-t);
if (t < 0) {
tmp[x].erase(tmp[x].find(y));
if (sz(tmp[x]) == 2) ok --;
}
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> q;
FOR(i,1,k+1) tmp[i].insert(-MOD), tmp[i].insert(MOD);
F0R(i,n) {
int x,t,a,b; cin >> x >> t >> a >> b;
ev.pb({a,1,t,x});
ev.pb({b+1,-1,t,x});
}
sort(all(ev));
for (auto a: ev) ad(a[2],a[3],a[1]);
}
int get(int z) {
if (ok != k) return -1;
int v = prev(m.ub(z))->s;
int x = S[0].query(v);
int y = S[1].query(v);
return max(x+z,y-z);
}
int main() {
init();
int co = 0;
for (auto& a: m) a.s = co++;
if (sz(m) > (1<<20)) {
exit(5);
}
for (auto& a: ev) a[1] *= 2;
F0R(i,q) {
int l,y; cin >> l >> y;
ev.pb({y,4,i,l});
}
sort(all(ev));
for (auto a: ev) {
if (a[1] == 4) {
ans[a[2]] = get(a[3]);
} else ad(a[2],a[3],a[1]);
}
F0R(i,q) cout << ans[i] << "\n";
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
211484 KB |
Output is correct |
2 |
Correct |
198 ms |
211484 KB |
Output is correct |
3 |
Correct |
206 ms |
211880 KB |
Output is correct |
4 |
Correct |
202 ms |
211880 KB |
Output is correct |
5 |
Correct |
205 ms |
211880 KB |
Output is correct |
6 |
Correct |
198 ms |
211884 KB |
Output is correct |
7 |
Correct |
200 ms |
211884 KB |
Output is correct |
8 |
Correct |
209 ms |
212084 KB |
Output is correct |
9 |
Correct |
205 ms |
212144 KB |
Output is correct |
10 |
Correct |
214 ms |
212232 KB |
Output is correct |
11 |
Correct |
207 ms |
212232 KB |
Output is correct |
12 |
Correct |
206 ms |
212232 KB |
Output is correct |
13 |
Correct |
206 ms |
212232 KB |
Output is correct |
14 |
Correct |
222 ms |
212232 KB |
Output is correct |
15 |
Correct |
221 ms |
212336 KB |
Output is correct |
16 |
Correct |
277 ms |
212336 KB |
Output is correct |
17 |
Correct |
199 ms |
212336 KB |
Output is correct |
18 |
Correct |
233 ms |
212336 KB |
Output is correct |
19 |
Correct |
225 ms |
212336 KB |
Output is correct |
20 |
Correct |
208 ms |
212336 KB |
Output is correct |
21 |
Correct |
200 ms |
212336 KB |
Output is correct |
22 |
Correct |
207 ms |
212340 KB |
Output is correct |
23 |
Correct |
227 ms |
212596 KB |
Output is correct |
24 |
Correct |
209 ms |
212596 KB |
Output is correct |
25 |
Correct |
207 ms |
212596 KB |
Output is correct |
26 |
Correct |
209 ms |
212596 KB |
Output is correct |
27 |
Correct |
231 ms |
212596 KB |
Output is correct |
28 |
Correct |
204 ms |
212596 KB |
Output is correct |
29 |
Correct |
207 ms |
212596 KB |
Output is correct |
30 |
Correct |
275 ms |
212596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
211484 KB |
Output is correct |
2 |
Correct |
198 ms |
211484 KB |
Output is correct |
3 |
Correct |
206 ms |
211880 KB |
Output is correct |
4 |
Correct |
202 ms |
211880 KB |
Output is correct |
5 |
Correct |
205 ms |
211880 KB |
Output is correct |
6 |
Correct |
198 ms |
211884 KB |
Output is correct |
7 |
Correct |
200 ms |
211884 KB |
Output is correct |
8 |
Correct |
209 ms |
212084 KB |
Output is correct |
9 |
Correct |
205 ms |
212144 KB |
Output is correct |
10 |
Correct |
214 ms |
212232 KB |
Output is correct |
11 |
Correct |
207 ms |
212232 KB |
Output is correct |
12 |
Correct |
206 ms |
212232 KB |
Output is correct |
13 |
Correct |
206 ms |
212232 KB |
Output is correct |
14 |
Correct |
222 ms |
212232 KB |
Output is correct |
15 |
Correct |
221 ms |
212336 KB |
Output is correct |
16 |
Correct |
277 ms |
212336 KB |
Output is correct |
17 |
Correct |
199 ms |
212336 KB |
Output is correct |
18 |
Correct |
233 ms |
212336 KB |
Output is correct |
19 |
Correct |
225 ms |
212336 KB |
Output is correct |
20 |
Correct |
208 ms |
212336 KB |
Output is correct |
21 |
Correct |
200 ms |
212336 KB |
Output is correct |
22 |
Correct |
207 ms |
212340 KB |
Output is correct |
23 |
Correct |
227 ms |
212596 KB |
Output is correct |
24 |
Correct |
209 ms |
212596 KB |
Output is correct |
25 |
Correct |
207 ms |
212596 KB |
Output is correct |
26 |
Correct |
209 ms |
212596 KB |
Output is correct |
27 |
Correct |
231 ms |
212596 KB |
Output is correct |
28 |
Correct |
204 ms |
212596 KB |
Output is correct |
29 |
Correct |
207 ms |
212596 KB |
Output is correct |
30 |
Correct |
275 ms |
212596 KB |
Output is correct |
31 |
Execution timed out |
5111 ms |
280400 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5133 ms |
313624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5093 ms |
313624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
211484 KB |
Output is correct |
2 |
Correct |
198 ms |
211484 KB |
Output is correct |
3 |
Correct |
206 ms |
211880 KB |
Output is correct |
4 |
Correct |
202 ms |
211880 KB |
Output is correct |
5 |
Correct |
205 ms |
211880 KB |
Output is correct |
6 |
Correct |
198 ms |
211884 KB |
Output is correct |
7 |
Correct |
200 ms |
211884 KB |
Output is correct |
8 |
Correct |
209 ms |
212084 KB |
Output is correct |
9 |
Correct |
205 ms |
212144 KB |
Output is correct |
10 |
Correct |
214 ms |
212232 KB |
Output is correct |
11 |
Correct |
207 ms |
212232 KB |
Output is correct |
12 |
Correct |
206 ms |
212232 KB |
Output is correct |
13 |
Correct |
206 ms |
212232 KB |
Output is correct |
14 |
Correct |
222 ms |
212232 KB |
Output is correct |
15 |
Correct |
221 ms |
212336 KB |
Output is correct |
16 |
Correct |
277 ms |
212336 KB |
Output is correct |
17 |
Correct |
199 ms |
212336 KB |
Output is correct |
18 |
Correct |
233 ms |
212336 KB |
Output is correct |
19 |
Correct |
225 ms |
212336 KB |
Output is correct |
20 |
Correct |
208 ms |
212336 KB |
Output is correct |
21 |
Correct |
200 ms |
212336 KB |
Output is correct |
22 |
Correct |
207 ms |
212340 KB |
Output is correct |
23 |
Correct |
227 ms |
212596 KB |
Output is correct |
24 |
Correct |
209 ms |
212596 KB |
Output is correct |
25 |
Correct |
207 ms |
212596 KB |
Output is correct |
26 |
Correct |
209 ms |
212596 KB |
Output is correct |
27 |
Correct |
231 ms |
212596 KB |
Output is correct |
28 |
Correct |
204 ms |
212596 KB |
Output is correct |
29 |
Correct |
207 ms |
212596 KB |
Output is correct |
30 |
Correct |
275 ms |
212596 KB |
Output is correct |
31 |
Execution timed out |
5111 ms |
280400 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
211484 KB |
Output is correct |
2 |
Correct |
198 ms |
211484 KB |
Output is correct |
3 |
Correct |
206 ms |
211880 KB |
Output is correct |
4 |
Correct |
202 ms |
211880 KB |
Output is correct |
5 |
Correct |
205 ms |
211880 KB |
Output is correct |
6 |
Correct |
198 ms |
211884 KB |
Output is correct |
7 |
Correct |
200 ms |
211884 KB |
Output is correct |
8 |
Correct |
209 ms |
212084 KB |
Output is correct |
9 |
Correct |
205 ms |
212144 KB |
Output is correct |
10 |
Correct |
214 ms |
212232 KB |
Output is correct |
11 |
Correct |
207 ms |
212232 KB |
Output is correct |
12 |
Correct |
206 ms |
212232 KB |
Output is correct |
13 |
Correct |
206 ms |
212232 KB |
Output is correct |
14 |
Correct |
222 ms |
212232 KB |
Output is correct |
15 |
Correct |
221 ms |
212336 KB |
Output is correct |
16 |
Correct |
277 ms |
212336 KB |
Output is correct |
17 |
Correct |
199 ms |
212336 KB |
Output is correct |
18 |
Correct |
233 ms |
212336 KB |
Output is correct |
19 |
Correct |
225 ms |
212336 KB |
Output is correct |
20 |
Correct |
208 ms |
212336 KB |
Output is correct |
21 |
Correct |
200 ms |
212336 KB |
Output is correct |
22 |
Correct |
207 ms |
212340 KB |
Output is correct |
23 |
Correct |
227 ms |
212596 KB |
Output is correct |
24 |
Correct |
209 ms |
212596 KB |
Output is correct |
25 |
Correct |
207 ms |
212596 KB |
Output is correct |
26 |
Correct |
209 ms |
212596 KB |
Output is correct |
27 |
Correct |
231 ms |
212596 KB |
Output is correct |
28 |
Correct |
204 ms |
212596 KB |
Output is correct |
29 |
Correct |
207 ms |
212596 KB |
Output is correct |
30 |
Correct |
275 ms |
212596 KB |
Output is correct |
31 |
Execution timed out |
5111 ms |
280400 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |