oj.uz

Submission #866772

# Submission time Handle Problem Language Result Execution time Memory
866772 2023-10-27T03:44:10 Z sleepntsheep Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 1000 ms 17592 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
using ll = long long;
#define N 200005

int n, q, t[N<<2], lz[N<<2];
pair<int, int> a[N];

void push(int v, int l, int r)
{
    if (lz[v])
    {
        t[v] += lz[v];
        if (l != r)
        {
            int m = (l+r)/2, vl=v+1, vr=vl+(m-l+1)*2;
            lz[vl]+=lz[v],lz[vr]+=lz[v];
        }
        lz[v] = 0;
    }
}

void update(int v, int l, int r, int x, int y, int k)
{
    push(v, l, r);
    if (r < x || y < l) return;
    if (x <= l && r <= y) { lz[v] += k; push(v, l, r); return; }
    int m = (l+r)/2, vl=v+1, vr=vl+(m-l+1)*2;
    update(vl, l, m, x, y, k), update(vr, m+1, r, x, y, k);
    t[v] = max(t[vl], t[vr]);
}

void update(int x, int y, int k) { update(0, 1, 2*n, x, y, k); }

int query(int v, int l, int r, int x, int y)
{
    push(v, l, r);
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) return t[v];
    int m = (l+r)/2, vl=v+1, vr=vl+(m-l+1)*2;
    return max(query(vl, l, m, x, y), query(vr, m+1, r, x, y));
}

int query(int x, int y) { return query(0, 1, 2*n, x, y); }

void compress()
{
    vector<int> C;
    C.reserve(2*n);
    for (int i = 0; i < n; ++i) C.push_back(a[i].first), C.push_back(a[i].second);
    sort(ALL(C));
    C.erase(unique(ALL(C)), C.end());
    for (int i = 0; i < n; ++i) a[i].first = lower_bound(ALL(C), a[i].first) - C.begin() + 1,
        a[i].second = lower_bound(ALL(C), a[i].second) - C.begin() + 1;
}

struct qry
{
    int l, r, i;
    bool operator<(const qry &o)
    {
        if (l/400 != o.l/400) return l<o.l;
        if (r!=o.r) return r>o.r;
        return i<o.i;
    }
} b[N];
int ans[N];

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
    compress();
    for (int i=  0;i<n;++i)cerr << a[i].first<< ' '<<a[i].second<<endl;
    cin >> q;
    for (int i = 0; i < q; ++i) cin >> b[i].l >> b[i].r, --b[i].l, --b[i].r, b[i].i = i;
    sort(b, b+q);
    int l = b[0].l, r = b[0].l-1;
    for (int i = 0; i < q; ++i)
    {
        auto [L, R, j] = b[i];
        while (l < L) update(a[l].first, a[l].second, -1), ++l;
        while (r > R) update(a[r].first, a[r].second, -1), --r;
        while (l > L) --l, update(a[l].first, a[l].second, 1);
        while (r < R) ++r, update(a[r].first, a[r].second, 1);
        push(0, 1, 2*n);
        ans[j] = t[0];
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 17256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 6740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 6740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 17592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 17256 KB Time limit exceeded
2 Halted 0 ms 0 KB -