oj.uz

Submission #936596

# Submission time Handle Problem Language Result Execution time Memory
936596 2024-03-02T09:40:12 Z heavylightdecomp New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 41612 KB 
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define X first
#define Y second
using pii = pair<int,int>;
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
//sim dor ris eni(x) rge range dud debug 2eni 2dor imie
#define sim template<class c
#define dor > debug& operator<<
#define ris return *this
#define eni(x) sim> typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i)
sim> struct rge { c b,e; };
sim> rge<c> range(c i, c j) { return rge<c>{i,j}; }
sim> auto dud(c* x)->decltype(cout<<*x,0);
sim> char dud(...);
#define cerr while(0) cerr
struct debug {
    ~debug() { cerr << endl; }
    eni(!=) { cerr << boolalpha << i; ris; }
    eni(==) { ris << range(all(i)); }
    sim, class b dor(pair<b,c> d) {
        ris << "(" << d.X << ", " << d.Y << ")";
    }
    sim dor(rge<c> d) {
        *this << "{";
        f0r(it,d.b,d.e) *this << ", " + 2*(it==d.b) << *it;
        ris << "}";
    }
};
#define imie(r...) " [" << #r << ": " << (r) << "] "
const int INF = 1e9, maxn = 3e5+5;
//store vectors of stores of the same type
//solve each type independently by a function that returns a vector
//then max the answer vectors
//if INF output -1
//solve function is basically sweep on the time ranges {l,r} {-1, x} encoding method
//use a set to denote positions of active stores
//1 indexing
int n,k,q;
vt<tuple<int,int,int>> stores[maxn]; //{pos, time_l, time_r}
pii queries[maxn];
int ans[maxn];
void solve(int type) { //BUG: multiset issues
    multiset<int> active;
    auto miss = [&](int p) {
        int res = INF;
        auto lb = active.lower_bound(p);
        if(lb != active.end()) {
            res = min(res, *lb - p);
        }
        if(lb != active.begin()) {
            res = min(res, p - *prev(lb));
        }
        return res;
    };
    //{time, 0/1/2, ref}
    //delete must be 0, insert must be 1, query = 2
    //inc excl ranges
    vt<tuple<int,int,int>> sweep;
    f0r(g,0,sz(stores[type])) {
        // debug() << "hi";
        auto [pos, l, r] = stores[type][g];
        debug() << imie(pos) << imie(l) << imie(r);
        sweep.pb({r+1, 0, g}); //BUG: exclusive ranges 💀
        sweep.pb({l, 1, g});
    }
    f0r(i,1,q+1) {
        auto [l, y] = queries[i];
        sweep.pb({y, 2, i});
    }
    sort(all(sweep));
    debug() << imie(sz(sweep));
    for(auto [t, hmm, ref] : sweep) {
        debug() << imie(t) << imie(hmm) << imie(ref);
        if(hmm == 0) {
            active.erase(active.find(get<0>(stores[type][ref])));
        } else if(hmm == 1) {
            active.insert(get<0>(stores[type][ref]));
        } else {
            int lol = miss(queries[ref].X);
            ans[ref] = max(ans[ref], lol);
        }
    }
}
signed main() {
    // vt<pii> wow = {{1,2}};
    // debug() << imie(wow);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    debug() << "hi am i here";
    f0r(i,0,maxn) ans[i] = -INF;
    f0r(i,1,n+1) {
        int x,t,a,b; cin >>x>>t>>a>>b;
        stores[t].pb({x,a,b});
    }
    f0r(i,1,q+1) {
        cin >> queries[i].X >> queries[i].Y;
    }
    debug() << "ayo";
    // f0r(i,1,k+1) {
    //     solve(i);
    // }
    f0r(i,1,k+1) {
        solve(i);
    }
    f0r(i,1,q+1) {
        if(ans[i] == INF) {
            cout << -1 << '\n';
        } else {
            cout << ans[i] << '\n';
        }
    }
}

Compilation message

new_home.cpp: In function 'void solve(int)':
new_home.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         auto [pos, l, r] = stores[type][g];
      |              ^
new_home.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         auto [l, y] = queries[i];
      |              ^
new_home.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto [t, hmm, ref] : sweep) {
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 11096 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 8 ms 10840 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 9 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 4 ms 10840 KB Output is correct
16 Correct 4 ms 11076 KB Output is correct
17 Correct 3 ms 10844 KB Output is correct
18 Correct 6 ms 10940 KB Output is correct
19 Correct 6 ms 11036 KB Output is correct
20 Correct 4 ms 10864 KB Output is correct
21 Correct 5 ms 10844 KB Output is correct
22 Correct 10 ms 11072 KB Output is correct
23 Correct 6 ms 10844 KB Output is correct
24 Correct 5 ms 10844 KB Output is correct
25 Correct 4 ms 11060 KB Output is correct
26 Correct 3 ms 10840 KB Output is correct
27 Correct 4 ms 11056 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct
29 Correct 2 ms 10844 KB Output is correct
30 Correct 3 ms 10844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 11096 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 8 ms 10840 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 9 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 4 ms 10840 KB Output is correct
16 Correct 4 ms 11076 KB Output is correct
17 Correct 3 ms 10844 KB Output is correct
18 Correct 6 ms 10940 KB Output is correct
19 Correct 6 ms 11036 KB Output is correct
20 Correct 4 ms 10864 KB Output is correct
21 Correct 5 ms 10844 KB Output is correct
22 Correct 10 ms 11072 KB Output is correct
23 Correct 6 ms 10844 KB Output is correct
24 Correct 5 ms 10844 KB Output is correct
25 Correct 4 ms 11060 KB Output is correct
26 Correct 3 ms 10840 KB Output is correct
27 Correct 4 ms 11056 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct
29 Correct 2 ms 10844 KB Output is correct
30 Correct 3 ms 10844 KB Output is correct
31 Correct 2682 ms 17124 KB Output is correct
32 Correct 98 ms 15444 KB Output is correct
33 Correct 153 ms 17204 KB Output is correct
34 Correct 2592 ms 17040 KB Output is correct
35 Correct 1018 ms 16340 KB Output is correct
36 Correct 161 ms 17500 KB Output is correct
37 Correct 186 ms 17188 KB Output is correct
38 Correct 76 ms 17208 KB Output is correct
39 Correct 76 ms 17220 KB Output is correct
40 Correct 67 ms 17256 KB Output is correct
41 Correct 1285 ms 16424 KB Output is correct
42 Correct 1779 ms 17056 KB Output is correct
43 Correct 2410 ms 16500 KB Output is correct
44 Correct 1053 ms 16680 KB Output is correct
45 Correct 345 ms 16328 KB Output is correct
46 Correct 80 ms 17268 KB Output is correct
47 Correct 94 ms 17036 KB Output is correct
48 Correct 63 ms 17116 KB Output is correct
49 Correct 147 ms 17136 KB Output is correct
50 Correct 895 ms 16956 KB Output is correct
51 Correct 88 ms 17080 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 41612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5020 ms 40548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 11096 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 8 ms 10840 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 9 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 4 ms 10840 KB Output is correct
16 Correct 4 ms 11076 KB Output is correct
17 Correct 3 ms 10844 KB Output is correct
18 Correct 6 ms 10940 KB Output is correct
19 Correct 6 ms 11036 KB Output is correct
20 Correct 4 ms 10864 KB Output is correct
21 Correct 5 ms 10844 KB Output is correct
22 Correct 10 ms 11072 KB Output is correct
23 Correct 6 ms 10844 KB Output is correct
24 Correct 5 ms 10844 KB Output is correct
25 Correct 4 ms 11060 KB Output is correct
26 Correct 3 ms 10840 KB Output is correct
27 Correct 4 ms 11056 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct
29 Correct 2 ms 10844 KB Output is correct
30 Correct 3 ms 10844 KB Output is correct
31 Correct 2682 ms 17124 KB Output is correct
32 Correct 98 ms 15444 KB Output is correct
33 Correct 153 ms 17204 KB Output is correct
34 Correct 2592 ms 17040 KB Output is correct
35 Correct 1018 ms 16340 KB Output is correct
36 Correct 161 ms 17500 KB Output is correct
37 Correct 186 ms 17188 KB Output is correct
38 Correct 76 ms 17208 KB Output is correct
39 Correct 76 ms 17220 KB Output is correct
40 Correct 67 ms 17256 KB Output is correct
41 Correct 1285 ms 16424 KB Output is correct
42 Correct 1779 ms 17056 KB Output is correct
43 Correct 2410 ms 16500 KB Output is correct
44 Correct 1053 ms 16680 KB Output is correct
45 Correct 345 ms 16328 KB Output is correct
46 Correct 80 ms 17268 KB Output is correct
47 Correct 94 ms 17036 KB Output is correct
48 Correct 63 ms 17116 KB Output is correct
49 Correct 147 ms 17136 KB Output is correct
50 Correct 895 ms 16956 KB Output is correct
51 Correct 88 ms 17080 KB Output is correct
52 Execution timed out 5023 ms 17876 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 11096 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 8 ms 10840 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 9 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 4 ms 10840 KB Output is correct
16 Correct 4 ms 11076 KB Output is correct
17 Correct 3 ms 10844 KB Output is correct
18 Correct 6 ms 10940 KB Output is correct
19 Correct 6 ms 11036 KB Output is correct
20 Correct 4 ms 10864 KB Output is correct
21 Correct 5 ms 10844 KB Output is correct
22 Correct 10 ms 11072 KB Output is correct
23 Correct 6 ms 10844 KB Output is correct
24 Correct 5 ms 10844 KB Output is correct
25 Correct 4 ms 11060 KB Output is correct
26 Correct 3 ms 10840 KB Output is correct
27 Correct 4 ms 11056 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct
29 Correct 2 ms 10844 KB Output is correct
30 Correct 3 ms 10844 KB Output is correct
31 Correct 2682 ms 17124 KB Output is correct
32 Correct 98 ms 15444 KB Output is correct
33 Correct 153 ms 17204 KB Output is correct
34 Correct 2592 ms 17040 KB Output is correct
35 Correct 1018 ms 16340 KB Output is correct
36 Correct 161 ms 17500 KB Output is correct
37 Correct 186 ms 17188 KB Output is correct
38 Correct 76 ms 17208 KB Output is correct
39 Correct 76 ms 17220 KB Output is correct
40 Correct 67 ms 17256 KB Output is correct
41 Correct 1285 ms 16424 KB Output is correct
42 Correct 1779 ms 17056 KB Output is correct
43 Correct 2410 ms 16500 KB Output is correct
44 Correct 1053 ms 16680 KB Output is correct
45 Correct 345 ms 16328 KB Output is correct
46 Correct 80 ms 17268 KB Output is correct
47 Correct 94 ms 17036 KB Output is correct
48 Correct 63 ms 17116 KB Output is correct
49 Correct 147 ms 17136 KB Output is correct
50 Correct 895 ms 16956 KB Output is correct
51 Correct 88 ms 17080 KB Output is correct
52 Execution timed out 5042 ms 41612 KB Time limit exceeded
53 Halted 0 ms 0 KB -