Submission #979342

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979342	2024-05-10T16:47:19 Z	Jarif_Rahman	New Home (APIO18_new_home)	C++17	10 / 100	886 ms	411100 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;

const int lim = 1e7;

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){}
}Nodes[lim];

int ls_node = 0;
Node* newNode(){
    return &Nodes[ls_node++];
}

struct sparse_segtree{
    Node* root = newNode();
    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 = newNode();
        if(!nd->r) nd->r = newNode();
        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	60 ms	391760 KB	Output is correct
2	Incorrect	70 ms	391600 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	391760 KB	Output is correct
2	Incorrect	70 ms	391600 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	886 ms	398740 KB	Output is correct
2	Correct	713 ms	394948 KB	Output is correct
3	Correct	694 ms	411100 KB	Output is correct
4	Correct	853 ms	400116 KB	Output is correct
5	Correct	558 ms	394184 KB	Output is correct
6	Correct	624 ms	394692 KB	Output is correct
7	Correct	623 ms	410960 KB	Output is correct
8	Correct	828 ms	399880 KB	Output is correct
9	Correct	864 ms	397032 KB	Output is correct
10	Correct	827 ms	395688 KB	Output is correct
11	Correct	602 ms	395012 KB	Output is correct
12	Correct	710 ms	395624 KB	Output is correct