답안 #62793 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62793	2018-07-30T04:52:17 Z	Benq	새 집 (APIO18_new_home)	C++11	5 / 100	5000 ms	313624 KB

new_home

#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
*/

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	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

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	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	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5133 ms	313624 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5093 ms	313624 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	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	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	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	-

답안 #62793

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0