Submission #743597

#	Time	Username	Problem	Language	Result	Execution time	Memory
743597		MilosMilutinovic	New Home (APIO18_new_home)	C++14	0 / 100	5084 ms	538256 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 * 20;
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 (a[i] <= l && r <= b[i]) {
//        printf("dodajem store[%d] na segm [%d, %d]\n", i, 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 * d, (-1) * d});
    } else if (R == M + 1) {
        segtree::modify(L, M, {(-L) * d, (+1) * d});
    } else {
        if (L == R) return;
        int mid = L + R >> 1;
        segtree::modify(L, mid, {(-L) * d, (+1) * d});
        segtree::modify(mid + 1, R, {(R) * d, (-1) * d});
    }
}
multiset<int> xs[N];
int tot_diff = 0, tp[N];
void Add(int v) {
    for (int i : segs[v]) {
//        printf("dodajem store[%d]\n", i);
        auto it = xs[t[i]].lower_bound(x[i]);
        if (it != xs[t[i]].end() && *it == x[i]) {
            xs[t[i]].insert(x[i]);
            tp[t[i]]++;
            if (tp[t[i]] == 1) tot_diff++;
            continue;
        }
        if (xs[t[i]].empty()) {
            addSeg(-1, x[i], +1);
            addSeg(x[i], M + 1, +1);
        } else if (it == xs[t[i]].begin()) {
            addSeg(-1, *it, -1);
            addSeg(-1, x[i], +1);
            addSeg(x[i], *it, +1);
        } else if (it == xs[t[i]].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[t[i]].insert(x[i]);
        tp[t[i]]++;
        if (tp[t[i]] == 1) tot_diff++;
    }
}
void Remove(int v) {
    for (int i : segs[v]) {
//        printf("brisem store[%d]\n", i);
        auto it = xs[t[i]].lower_bound(x[i]);
        if (xs[t[i]].size() == 1) {
            addSeg(-1, x[i], -1);
            addSeg(x[i], M + 1, -1);
        } else if (it == xs[t[i]].begin()) {
            addSeg(-1, x[i], -1);
            addSeg(x[i], *next(it), -1);
            addSeg(-1, *next(it), +1);
        } else if (it == prev(xs[t[i]].end())) {
            addSeg(*prev(it), x[i], -1);
            addSeg(x[i], M + 1, -1);
            addSeg(*prev(it), M + 1, +1);
        } else {
            addSeg(*prev(it), x[i], -1);
            addSeg(x[i], *next(it), -1);
            addSeg(*prev(it), *next(it), +1);
        }
        xs[t[i]].erase(it);
        tp[t[i]]--;
        if (tp[t[i]] == 0) tot_diff--;
    }
}
void solve(int v, int l, int r) {
    if (!v) return;
    Add(v);
    if (l == r) {
        for (int i : QS[v]) {
            printf("odgovaram na query[%d] tot_diff = %d\n", i, tot_diff);
            ans[i] = (tot_diff == k ? segtree::query(p[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, &k, &q);
    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;
}
/*
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
*/

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:145:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     scanf("%d%d%d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:152:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |     for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:153:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |     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