| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 66476 | Benq | 새 집 (APIO18_new_home) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
void checkmx(int& a, int b) { a = max(a,b); }
void checkmn(int& a, int b) { a = min(a,b); }
int getPos(vi& v, int x) { return ub(all(v),x)-v.begin()-1; }
template<int SZ> struct seg {
vector<array<int,4>> todo; // query minimum, interval min operations
vi num;
int mx[2][SZ];
void pull(int ind) {
F0R(i,2) mx[i][ind] = max(mx[i][2*ind],mx[i][2*ind+1]);
int t = min(mx[0][2*ind],mx[0][2*ind+1]);
if (t != mx[0][ind]) checkmx(t,mx[1][ind]);
}
void build(int ind, int L, int R) {
if (L == R) { mx[0][ind] = 2*MOD; mx[1][ind] = -2*MOD; return; }
int M = (L+R)/2;
build(2*ind,L,M); build(2*ind+1,M+1,R);
pull(ind);
}
void build() {
num.pb(-MOD);
for (auto a: todo) num.pb(a[2]), num.pb(a[3]+1);
sort(all(num)); num.erase(unique(all(num)),num.end());
build(1,0,sz(num)-1);
}
void push(int ind, int L, int R) {
if (L == R) return;
F0R(i,2) checkmn(mx[0][2*ind+i],mx[0][ind]);
}
void modify(int x, int y, int t, int ind, int L, int R) {
if (R < x || y < L || mx[0][ind] <= t) return;
push(ind,L,R);
if (x <= L && R <= y && mx[1][ind] < t) { mx[0][ind] = t; return; }
if (L == R) return;
int M = (L+R)/2;
modify(x,y,t,2*ind,L,M);
modify(x,y,t,2*ind+1,M+1,R);
pull(ind);
}
void modify(int x, int y, int t) {
// cout << "OOPS " << x << " " << y << " " << t << " " << getPos(num,x) << " " << getPos(num,y) << "\n";
modify(getPos(num,x),getPos(num,y),t,1,0,sz(num)-1);
}
int query(int x, int ind, int L, int R) {
push(ind,L,R);
if (L == R) return mx[0][ind];
int M = (L+R)/2;
if (x <= M) return query(x,2*ind,L,M);
return query(x,2*ind+1,M+1,R);
}
int query(int x) {
// cout << "HUH " << getPos(num,x) << "\n";
return query(getPos(num,x),1,0,sz(num)-1);
}
};
int n,k,q, ans[MX];
seg<1<<20> S[2];
map<pi,int> type[MX];
vector<array<int,5>> mod;
vector<array<int,3>> query;
ostream& operator <<(ostream& os, const pair<pi,int>& p) {
os << p.f.f << " " << p.f.s << " " << p.s << " | ";
return os;
}
void ins(int x, pair<pi,int> a, pair<pi,int> b) {
// cout << x << " | " << a << b << "\n";
if (a.f.f == -MOD && b.f.f == MOD) {
S[0].todo.pb({MOD,-MOD,a.s,x});
S[1].todo.pb({-MOD,MOD,a.s,x});
} else {
S[0].todo.pb({(a.f.f+b.f.f)/2,a.f.f,a.s,x}); // all x <= (a.f.f+b.f.f)/2
S[1].todo.pb({(a.f.f+b.f.f)/2+1,b.f.f,a.s,x});
}
}
pair<pi,int> getNex(auto& a, auto b) {
b = next(b);
if (b == a.end()) return {{MOD,-1},1};
return *b;
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> q;
F0R(i,n) {
int x,t,a,b; cin >> x >> t >> a >> b;
mod.pb({a,1,t,x,i});
mod.pb({b+1,-1,t,x,i});
}
FOR(i,1,k+1) type[i][{-MOD,-1}] = 1;
sort(all(mod));
for (auto a: mod) {
pi t = {a[3],a[4]};
if (a[1] == 1) {
type[a[2]][t] = 0;
auto it = type[a[2]].find(t);
ins(a[0]-1,*prev(it),getNex(type[a[2]],it));
prev(it)->s = it->s = a[0];
} else {
auto it = type[a[2]].find(t);
ins(a[0]-1,*prev(it),*it);
ins(a[0]-1,*it,getNex(type[a[2]],it));
prev(it)->s = a[0];
type[a[2]].erase(it);
}
}
FOR(i,1,k+1) ins(1e8,*type[i].begin(),getNex(type[i],type[i].begin()));
}
void solve0() {
sort(query.rbegin(),query.rend());
S[0].build();
sort(all(S[0].todo));
for (auto a: query) {
while (sz(S[0].todo)) {
auto x = S[0].todo.back();
if (x[0] < a[0]) break;
S[0].modify(x[2],x[3],x[1]);
S[0].todo.pop_back();
}
checkmx(ans[a[2]],a[0]-S[0].query(a[1]));
}
}
void solve1() {
reverse(all(query));
S[1].build();
sort(all(S[1].todo)); reverse(all(S[1].todo));
for (auto a: query) {
while (sz(S[1].todo)) {
auto x = S[1].todo.back();
if (x[0] > a[0]) break;
S[1].modify(x[2],x[3],-x[1]);
S[1].todo.pop_back();
}
checkmx(ans[a[2]],-S[1].query(a[1])-a[0]);
}
}
int main() {
init();
F0R(i,q) {
int l,y; cin >> l >> y;
query.pb({l,y,i});
}
solve0();
solve1();
F0R(i,q) {
if (ans[i] > (1e8)) cout << -1;
else cout << ans[i];
cout << "\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
*/