Submission #743559

#	Time	Username	Problem	Language	Result	Execution time	Memory
743559		MilosMilutinovic	New Home (APIO18_new_home)	C++14	0 / 100	5070 ms	461176 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int M = 1e8 + 10;
const int K = 5e6 + 10;
const int F = N * 23;
int n, q, k, x[N], t[N], a[N], b[N], p[N], y[N], ls[F], rs[F], root, tsz;
ll ans[N];
vector<int> segs[F], QS[F];
namespace segtree {
    pair<ll, int> st[K];
    int root, tsz, ls[K], rs[K];
    void modify(int& v, int l, int r, int ql, int qr, pair<ll, int> f) {
        if (l > r || l > qr || r < ql) return;
        if (!v) v = ++tsz;
        if (v >= K) while (true) {}
        if (ql <= l && r <= qr) {
            st[v].first += f.first;
            st[v].second += f.second;
            return;
        }
        int mid = l + r >> 1;
        modify(ls[v], l, mid, ql, qr, f);
        modify(rs[v], mid + 1, r, ql, qr, f);
    }
    void modify(int l, int r, pair<ll, int> f) { modify(root, 1, M, l, r, f); }
    pair<ll, int> query(int v, int l, int r, int p) {
        if (!v) return {0LL, 0};
        if (l == r) return st[v];
        int mid = l + r >> 1;
        pair<ll, int> f;
        if (p <= mid) f = query(ls[v], l, mid, p);
        else f = query(rs[v], mid + 1, r, p);
        return {st[v].first + f.first, st[v].second + f.second};
    }
    ll query(int p) {
        pair<ll, int> f = query(root, 1, M, p);
        return f.first + p * 1LL * f.second;
    }
};
void insStore(int& v, int l, int r, int i) {
    if (l > r || l > b[i] || r < a[i]) return;
    if (!v) v = ++tsz;
    if (l <= a[i] && b[i] <= r) {
//        printf("dodajem store na segm [%d, %d]\n", l, r);
        segs[v].push_back(i);
        return;
    }
    int mid = l + r >> 1;
    insStore(ls[v], l, mid, i);
    insStore(rs[v], mid + 1, r, i);
}
void insQuery(int& v, int l, int r, int i) {
    if (!v) v = ++tsz;
    if (l == r) { QS[v].push_back(i); return; }
    int mid = l + r >> 1;
    if (y[i] <= mid)
        insQuery(ls[v], l, mid, i);
    else
        insQuery(rs[v], mid + 1, r, i);
}
void addSeg(int L, int R, int d) {
    if (L == -1) {
        segtree::modify(1, R, {R, -1});
    } else if (R == M + 1) {
        segtree::modify(L, M, {-L, +1});
    } else {
        if (L == R) return;
        int mid = L + R >> 1;
        segtree::modify(L, mid, {-L, +1});
        segtree::modify(mid + 1, R, {R, -1});
    }
}
multiset<int> xs;
int tot_diff = 0;
int tp[N];
void Add(int v) {
    for (int i : segs[v]) {
        auto it = xs.lower_bound(x[i]);
        if (it != xs.end() && *it == x[i]) {
            xs.insert(a[i]);
            continue;
        }
        if (xs.empty()) {
            addSeg(-1, x[i], +1);
            addSeg(x[i], M + 1, +1);
        } else if (it == xs.begin()) {
            addSeg(-1, *it, -1);
            addSeg(-1, x[i], +1);
            addSeg(x[i], *it, +1);
        } else if (it == xs.end()) {
            addSeg(*it, M + 1, -1);
            addSeg(*prev(it), x[i], +1);
            addSeg(x[i], M + 1, +1);
        } else {
            int L = *prev(it), R = *it;
            addSeg(L, R, -1);
            addSeg(L, x[i], +1);
            addSeg(x[i], R, +1);
        }
        xs.insert(x[i]);
        tp[t[i]]++;
        if (tp[t[i]] == 1) tot_diff++;
    }
}
void Remove(int v) {

}
void solve(int v, int l, int r) {
    if (!v) return;
    Add(v);
    if (l == r) {
        for (int i : QS[v]) ans[i] = (tot_diff == k ? segtree::query(y[i]) : -1);
        Remove(v);
        return;
    }
    int mid = l + r >> 1;
    solve(ls[v], l, mid);
    solve(rs[v], mid + 1, r);
    Remove(v);
}
int main() {
    scanf("%d%d%d", &n, &q, &k);
    for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
    for (int i = 1; i <= q; i++) scanf("%d%d", &p[i], &y[i]);
    for (int i = 1; i <= n; i++) insStore(root, 1, M, i);
    for (int i = 1; i <= q; i++) insQuery(root, 1, M, i);
    solve(root, 1, M);
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0;
}
/*
1 1 1
1000000 1 1 1
1 1
*/

Compilation message (stderr)

new_home.cpp: In function 'void segtree::modify(int&, int, int, int, int, std::pair<long long int, int>)':
new_home.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int mid = l + r >> 1;
      |                   ~~^~~
new_home.cpp: In function 'std::pair<long long int, int> segtree::query(int, int, int, int)':
new_home.cpp:31:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = l + r >> 1;
      |                   ~~^~~
new_home.cpp: In function 'void insStore(int&, int, int, int)':
new_home.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'void insQuery(int&, int, int, int)':
new_home.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'void addSeg(int, int, int)':
new_home.cpp:70:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d%d%d", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:125:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:126:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     for (int i = 1; i <= q; i++) scanf("%d%d", &p[i], &y[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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