Submission #742961

#	Time	Username	Problem	Language	Result	Execution time	Memory
742961		PixelCat	New Home (APIO18_new_home)	C++14	0 / 100	584 ms	80840 KiB

new_home

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 300030; // = MAXQ
const int INF = (int)(3e13) + 10;

struct Line {
    int m, c;  // mx + c
    Line(int _m = 0, int _c = 0): m(_m), c(_c) {}
    int operator()(int x) {
        return m * x + c;
    }
};
Line operator+(const Line& a, const Line& b) {
    return Line(a.m + b.m, a.c + b.c);
}
Line operator-(const Line& a, const Line& b) {
    return Line(a.m - b.m, a.c - b.c);
}
Line operator-(const Line& ln) {
    return Line(-ln.m, -ln.c);
}

struct Event {
    int pos, type;
    Line ln;
    // type: 0 for line addition, 1~q for query
}; deque<Event> dq;

void add_line(int l, int r, Line ln) {
    dq.eb((Event){ l, 0, ln });
    dq.eb((Event){ r + 1, 0, -ln });
}

int ans[MAXN];
vector<int> pos[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^= nya
    int n, mxk, q; cin >> n >> mxk >> q;
    For(i, 1, n) {
        int x, t, a, b; cin >> x >> t >> a >> b;
        pos[t].eb(x);
    }
    For(i, 1, mxk) {
        if(!sz(pos[i])) {
            while(q--) cout << "-1\n";
            return 0;
        }
        sort(all(pos[i]));
        add_line(1, pos[i][0], Line(-1, pos[i][0]));
        add_line(pos[i].back() + 1, 1e8, Line(1, -pos[i].back()));
        For(j, 0, sz(pos[i]) - 2) {
            int l = pos[i][j];
            int r = pos[i][j + 1];
            int m = (l + r) / 2;
            add_line(l + 1, m, Line(1, -l));
            add_line(m + 1, r, Line(-1, r));
        }
    }
    For(i, 1, q) {
        int x, t; cin >> x >> t;
        dq.eb((Event){ x, i, Line() });
    }
    sort(all(dq), [&](auto a, auto b) {
        if(a.pos != b.pos) return a.pos < b.pos;
        return a.type < b.type;
    });
    Line cur(0, 0);
    while(sz(dq)) {
        auto e = dq.front(); dq.pop_front();
        if(e.type == 0) {
            cur = cur + e.ln;
        } else {
            ans[e.type] = cur(e.pos);
        }
    }
    For(i, 1, q) cout << ans[i] << "\n";
    return 0;
}

/*

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20