Submission #698817

#	Time	Username	Problem	Language	Result	Execution time	Memory
698817		haxorman	New Home (APIO18_new_home)	C++14	0 / 100	1 ms	980 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 3e5 + 7;
const int SZ = 1e8 + 7;

struct T {
    int mn, mx;
    bitset<401> bs;
};

struct LazySeg {
    T val, lazy;
    LazySeg *Left, *Right;
 
    LazySeg () {
        val.mn = lazy.mn = INT_MAX;
        val.mx = lazy.mx = INT_MIN;
        val.bs = lazy.bs = 0;
 
        Left = Right = nullptr;
    }
    
    void push(int l, int r) {
        if (!Left) Left = new LazySeg();
        if (!Right) Right = new LazySeg();
 
        val.mn = min(val.mn, lazy.mn);
        val.mx = max(val.mx, lazy.mx);
        val.bs |= lazy.bs;
        if (l != r) {
            Left -> lazy.mn = min(Left -> lazy.mn, lazy.mn);
            Left -> lazy.mx = min(Left -> lazy.mx, lazy.mx);
            Left -> lazy.bs |= lazy.bs;

            Right -> lazy.mn = min(Right -> lazy.mn, lazy.mn);
            Right -> lazy.mx = min(Right -> lazy.mx, lazy.mx);
            Right -> lazy.bs |= lazy.bs;
        }
        lazy.mn = INT_MAX;
        lazy.mx = INT_MIN;
        lazy.bs = 0;
    }
 
    void update(int lo, int hi, bool flag, int up, int l, int r) {
        push(l, r);
        if (r < lo || l > hi) {
            return;
        }
 
        if (lo <= l && r <= hi) {
            if (!flag) {
                lazy.mn = min(lazy.mn, up);
                lazy.mx = max(lazy.mx, up);
            }
            else {
                lazy.bs[up] = 1;
            }
            push(l, r);
            return;
        }
 
        int mid = (l + r) / 2;
        Left -> update(lo, hi, flag, up, l, mid);
        Right -> update(lo, hi, flag, up, mid + 1, r);
        
        val.mn = min(Left -> val.mn, Right -> val.mn);
        val.mx = min(Left -> val.mx, Right -> val.mx);
        val.bs = (Left -> val.bs | Right -> val.bs);
    }
    
    T cmb(T a, T b) {
        T ret;
        ret.mn = min(a.mn, b.mn);
        ret.mx = max(a.mx, b.mx);
        ret.bs = (a.bs | b.bs);

        return ret;
    }

    T query(int pos, int l, int r) {
        push(l, r);
        if (l == r) {
            return val;
        }
 
        int mid = (l + r) / 2;
        if (pos <= mid) {
            return Left -> query(pos, l, mid);
        }
        else {
            return Right -> query(pos, mid + 1, r);
        }
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
    int n, k, q;
    cin >> n >> k >> q;
    
    LazySeg *seg = new LazySeg();
    
    for (int i = 0; i < n; ++i) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;

        seg -> update(a, b, false, x, 1, SZ);
        seg -> update(a, b, true, t, 1, SZ);
    }

    while (q--) {
        int l, y;
        cin >> l >> y;
        
        T res = seg -> query(y, 1, SZ);
        if (res.bs.count() != k) {
            cout << "-1\n";
        }
        else {
            cout << max(abs(res.mn - l), abs(res.mx - l)) << "\n";
        }
    }
}

Compilation message (stderr)

new_home.cpp: In function 'int32_t main()':
new_home.cpp:120:28: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  120 |         if (res.bs.count() != k) {
      |             ~~~~~~~~~~~~~~~^~~~

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