Submission #979339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979339	2024-05-10T16:42:05 Z	Jarif_Rahman	New Home (APIO18_new_home)	C++17	10 / 100	1229 ms	385752 KB

new_home

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct sparse_segtree{
    struct Node{
        ll inc = 0, dec = 0;
        bool binc = 0, bdec = 0;
        Node *l = nullptr, *r = nullptr;

        Node(){}
        Node(Node *_l, Node *_r): l(_l), r(_r){}
    };

    Node* root = new Node();
    int n = 1;
    sparse_segtree(int _n){
        while(n < _n) n*=2;
    }

    void add(int l, int r, Node* nd, int a, int b, ll x, bool inc){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            if(inc) nd->inc = max(nd->inc, x+a-l), nd->binc = 1;
            else nd->dec = max(nd->dec, x-a+l), nd->bdec = 1;
            return;
        }
        int m = (a+b)/2;
        if(!nd->l) nd->l = new Node();
        if(!nd->r) nd->r = new Node();
        add(l, r, nd->l, a, m, x, inc);
        add(l, r, nd->r, m+1, b, x, inc);
    }
    void add(int l, int r, ll x, bool inc){
        add(l, r, root, 0, n-1, x, inc);
    }

    ll get(int i){
        Node* nd = root;
        int a = 0, b = n-1;
        ll mx = 0;
        while(nd){
            if(nd->binc) mx = max(mx, nd->inc+i-a);
            if(nd->bdec) mx = max(mx, nd->dec-i+a);
            int m = (a+b)/2;
            if(i <= m) nd = nd->l, b = m;
            else nd = nd->r, a = m+1;
        }
        return mx;
    }
};

const int L = 1e8+5;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k, q; cin >> n >> k >> q;
    vector<vector<int>> stores(k);
    for(int i = 0; i < n; i++){
        int x, t, a, b; cin >> x >> t >> a >> b; t--;
        stores[t].push_back(x);
    }
    for(auto &s: stores) sort(s.begin(), s.end());

    sparse_segtree S(L);
    for(auto s: stores){
        if(s.empty()){
            while(q--) cout << "-1\n";
            exit(0);
        }
        int m = s.size();
        S.add(0, s[0], s[0], false); //abs(0-s[0])
        for(int i = 0; i+1 < m; i++){
            int md = (s[i]+s[i+1])/2;
            if(md > s[i]) S.add(s[i]+1, md, 1, true);
            S.add(md+1, s[i+1], s[i+1]-md-1, false);
        }
        S.add(s[m-1]+1, L-1, 1, true);
    }

    while(q--){
        int l, y; cin >> l >> y;
        cout << S.get(l) << "\n";
    }
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1229 ms	359812 KB	Output is correct
2	Correct	968 ms	384560 KB	Output is correct
3	Correct	849 ms	245324 KB	Output is correct
4	Correct	1142 ms	340804 KB	Output is correct
5	Correct	765 ms	383792 KB	Output is correct
6	Correct	888 ms	384752 KB	Output is correct
7	Correct	804 ms	245332 KB	Output is correct
8	Correct	1079 ms	340356 KB	Output is correct
9	Correct	1182 ms	373032 KB	Output is correct
10	Correct	1123 ms	385752 KB	Output is correct
11	Correct	816 ms	377940 KB	Output is correct
12	Correct	949 ms	383536 KB	Output is correct