oj.uz

Submission #698817

# Submission time Handle Problem Language Result Execution time Memory
698817 2023-02-14T10:15:58 Z haxorman New Home (APIO18_new_home) C++14
0 / 100
 1 ms 980 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -