답안 #62794 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62794	2018-07-30T04:53:54 Z	Benq	새 집 (APIO18_new_home)	C++11	5 / 100	5000 ms	245788 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<<18> 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	68 ms	63736 KB	Output is correct
2	Correct	65 ms	63736 KB	Output is correct
3	Correct	82 ms	63800 KB	Output is correct
4	Correct	74 ms	63800 KB	Output is correct
5	Correct	63 ms	63852 KB	Output is correct
6	Correct	83 ms	64056 KB	Output is correct
7	Correct	68 ms	64056 KB	Output is correct
8	Correct	85 ms	64100 KB	Output is correct
9	Correct	81 ms	64252 KB	Output is correct
10	Correct	82 ms	64272 KB	Output is correct
11	Correct	69 ms	64272 KB	Output is correct
12	Correct	74 ms	64272 KB	Output is correct
13	Correct	81 ms	64272 KB	Output is correct
14	Correct	84 ms	64272 KB	Output is correct
15	Correct	80 ms	64272 KB	Output is correct
16	Correct	80 ms	64272 KB	Output is correct
17	Correct	86 ms	64272 KB	Output is correct
18	Correct	93 ms	64272 KB	Output is correct
19	Correct	88 ms	64272 KB	Output is correct
20	Correct	77 ms	64272 KB	Output is correct
21	Correct	73 ms	64272 KB	Output is correct
22	Correct	68 ms	64456 KB	Output is correct
23	Correct	64 ms	64456 KB	Output is correct
24	Correct	69 ms	64456 KB	Output is correct
25	Correct	79 ms	64456 KB	Output is correct
26	Correct	75 ms	64456 KB	Output is correct
27	Correct	69 ms	64456 KB	Output is correct
28	Correct	83 ms	64456 KB	Output is correct
29	Correct	71 ms	64456 KB	Output is correct
30	Correct	70 ms	64456 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	63736 KB	Output is correct
2	Correct	65 ms	63736 KB	Output is correct
3	Correct	82 ms	63800 KB	Output is correct
4	Correct	74 ms	63800 KB	Output is correct
5	Correct	63 ms	63852 KB	Output is correct
6	Correct	83 ms	64056 KB	Output is correct
7	Correct	68 ms	64056 KB	Output is correct
8	Correct	85 ms	64100 KB	Output is correct
9	Correct	81 ms	64252 KB	Output is correct
10	Correct	82 ms	64272 KB	Output is correct
11	Correct	69 ms	64272 KB	Output is correct
12	Correct	74 ms	64272 KB	Output is correct
13	Correct	81 ms	64272 KB	Output is correct
14	Correct	84 ms	64272 KB	Output is correct
15	Correct	80 ms	64272 KB	Output is correct
16	Correct	80 ms	64272 KB	Output is correct
17	Correct	86 ms	64272 KB	Output is correct
18	Correct	93 ms	64272 KB	Output is correct
19	Correct	88 ms	64272 KB	Output is correct
20	Correct	77 ms	64272 KB	Output is correct
21	Correct	73 ms	64272 KB	Output is correct
22	Correct	68 ms	64456 KB	Output is correct
23	Correct	64 ms	64456 KB	Output is correct
24	Correct	69 ms	64456 KB	Output is correct
25	Correct	79 ms	64456 KB	Output is correct
26	Correct	75 ms	64456 KB	Output is correct
27	Correct	69 ms	64456 KB	Output is correct
28	Correct	83 ms	64456 KB	Output is correct
29	Correct	71 ms	64456 KB	Output is correct
30	Correct	70 ms	64456 KB	Output is correct
31	Execution timed out	5033 ms	129104 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2893 ms	245788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	63736 KB	Output is correct
2	Correct	65 ms	63736 KB	Output is correct
3	Correct	82 ms	63800 KB	Output is correct
4	Correct	74 ms	63800 KB	Output is correct
5	Correct	63 ms	63852 KB	Output is correct
6	Correct	83 ms	64056 KB	Output is correct
7	Correct	68 ms	64056 KB	Output is correct
8	Correct	85 ms	64100 KB	Output is correct
9	Correct	81 ms	64252 KB	Output is correct
10	Correct	82 ms	64272 KB	Output is correct
11	Correct	69 ms	64272 KB	Output is correct
12	Correct	74 ms	64272 KB	Output is correct
13	Correct	81 ms	64272 KB	Output is correct
14	Correct	84 ms	64272 KB	Output is correct
15	Correct	80 ms	64272 KB	Output is correct
16	Correct	80 ms	64272 KB	Output is correct
17	Correct	86 ms	64272 KB	Output is correct
18	Correct	93 ms	64272 KB	Output is correct
19	Correct	88 ms	64272 KB	Output is correct
20	Correct	77 ms	64272 KB	Output is correct
21	Correct	73 ms	64272 KB	Output is correct
22	Correct	68 ms	64456 KB	Output is correct
23	Correct	64 ms	64456 KB	Output is correct
24	Correct	69 ms	64456 KB	Output is correct
25	Correct	79 ms	64456 KB	Output is correct
26	Correct	75 ms	64456 KB	Output is correct
27	Correct	69 ms	64456 KB	Output is correct
28	Correct	83 ms	64456 KB	Output is correct
29	Correct	71 ms	64456 KB	Output is correct
30	Correct	70 ms	64456 KB	Output is correct
31	Execution timed out	5033 ms	129104 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	63736 KB	Output is correct
2	Correct	65 ms	63736 KB	Output is correct
3	Correct	82 ms	63800 KB	Output is correct
4	Correct	74 ms	63800 KB	Output is correct
5	Correct	63 ms	63852 KB	Output is correct
6	Correct	83 ms	64056 KB	Output is correct
7	Correct	68 ms	64056 KB	Output is correct
8	Correct	85 ms	64100 KB	Output is correct
9	Correct	81 ms	64252 KB	Output is correct
10	Correct	82 ms	64272 KB	Output is correct
11	Correct	69 ms	64272 KB	Output is correct
12	Correct	74 ms	64272 KB	Output is correct
13	Correct	81 ms	64272 KB	Output is correct
14	Correct	84 ms	64272 KB	Output is correct
15	Correct	80 ms	64272 KB	Output is correct
16	Correct	80 ms	64272 KB	Output is correct
17	Correct	86 ms	64272 KB	Output is correct
18	Correct	93 ms	64272 KB	Output is correct
19	Correct	88 ms	64272 KB	Output is correct
20	Correct	77 ms	64272 KB	Output is correct
21	Correct	73 ms	64272 KB	Output is correct
22	Correct	68 ms	64456 KB	Output is correct
23	Correct	64 ms	64456 KB	Output is correct
24	Correct	69 ms	64456 KB	Output is correct
25	Correct	79 ms	64456 KB	Output is correct
26	Correct	75 ms	64456 KB	Output is correct
27	Correct	69 ms	64456 KB	Output is correct
28	Correct	83 ms	64456 KB	Output is correct
29	Correct	71 ms	64456 KB	Output is correct
30	Correct	70 ms	64456 KB	Output is correct
31	Execution timed out	5033 ms	129104 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #62794

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