oj.uz

Submission #982032

# Submission time Handle Problem Language Result Execution time Memory
982032 2024-05-13T18:13:52 Z asdasdqwer Plahte (COCI17_plahte) C++14
0 / 160
 218 ms 31488 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii array<int,2>

struct Segtree {
    int n;
    vector<vector<int>> seg;
    
    Segtree(int sz, vector<int> &a) {
        n=1;
        while (n<sz)n*=2;
        seg.resize(2*n);
        build(a, 0, 0, n);
    }
    
    void merge(int x) {
        size_t p1 = 0;
        size_t p2 = 0;
        size_t len = (seg[2*x+1].size() + seg[2*x+2].size());
    
        for (;p1+p2<len;) {
            if ((p2 == seg[2*x+2].size()) || (p1 != seg[2*x+1].size() && seg[2*x+1][p1] < seg[2*x+2][p2])) {
                seg[x].push_back(seg[2*x+1][p1++]);
            }
    
            else {
                seg[x].push_back(seg[2*x+2][p2++]);
            }
        }
    }
    
    void build(vector<int> &a, int x, int lx, int rx) {
        if (rx-lx==1) {
            if (lx < (int)a.size()) {
                seg[x] = {a[lx]};
            }
            return;
        }
    
        int m=(lx+rx)/2;
        build(a, 2*x+1, lx, m);
        build(a, 2*x+2, m, rx);
    
        merge(x);
    }
    
    int get(int l, int r, int lw, int up, int x, int lx, int rx) {
        // lw and up inclusive
        if (lx >= r || rx <= l) return 0;
        if (lx >= l && rx <= r) {
            if (seg[x][0] > up || seg[x].back() < lw) {
                return 0;
            }
    
            auto it = upper_bound(seg[x].begin(), seg[x].end(), up);

            if (it != seg[x].end() && *it < lw) {
                return 0;
            }
    
            int dis = (int)distance(seg[x].begin(), it);
            auto it2 = lower_bound(seg[x].begin(), seg[x].end(), lw);

            if (*it2 > up) {
                return 0;
            }
    
            int dis2 = (int)distance(seg[x].begin(), it2);
            dis -= dis2;

            return dis;
        }
    
        int m=(lx+rx)/2;
        return get(l, r, lw, up, 2*x+1, lx, m) + get(l, r, lw, up, 2*x+2, m, rx);
    }
    
    int get(int l, int r, int lw, int up) {
        return get(l, r, lw, up, 0, 0, n);
    } 
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,m;cin>>n>>m;
    vector<array<pii, 2>> v(n);
    for (auto &x:v) {
        cin>>x[0][0]>>x[0][1]>>x[1][0]>>x[1][1];
    }

    vector<pii> pts(m);
    for (auto &x:pts) {
        cin>>x[0]>>x[1];
        int tmp;cin>>tmp;
    }

    sort(pts.begin(), pts.end());

    vector<int> yval;
    for (auto &x:pts) {
        yval.push_back(x[1]);
    }

    Segtree sg(m, yval);

    for (auto &x : v) {
        pii aaa = {x[0][0], -1};
        auto it1 = upper_bound(pts.begin(), pts.end(), aaa);
        if (it1 == pts.end()) {
            cout<<0<<"\n";
            continue;
        }

        int dis1 = distance(pts.begin(), it1);
        aaa = {x[1][0], ((int)1e9)+1};
        auto it2 = upper_bound(pts.begin(), pts.end(), aaa);

        if (it2 == pts.begin()) {
            cout<<0<<"\n";
            continue;
        }        

        it2 = prev(it2);
        int dis2 = distance(pts.begin(), it2);

        cout<<sg.get(dis1, dis2+1, x[0][1], x[1][1])<<"\n";
    }
}

Subtask #1
0 / 32.0

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

Subtask #2
0 / 32.0

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

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 32.0

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