oj.uz

Submission #998626

# Submission time Handle Problem Language Result Execution time Memory
998626 2024-06-14T11:44:13 Z VMaksimoski008 Examination (JOI19_examination) C++17
0 / 100
 134 ms 41920 KB 
#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

// Query/Update: O(Nlog^2N)
// Memory: O(NlogN)
struct BIT_2D_Offline {
    int n;
    vector<vector<ll> > tree, vals;

    BIT_2D_Offline(int n, vector<pii> &U) : n(n), vals(n+1), tree(n+1) {
        sort(U.begin(), U.end(), [&](pii &a, pii &b) { return a.second < b.second; });
        for(int i=1; i<=n; i++) vals[i].push_back( 0 );

        for(auto &[x, y]: U)
            for(; x<=n; x+=x&-x)
                if(vals[x].back() != y) vals[x].push_back(y);

        for(int i=1; i<=n; i++) tree[i].resize( vals[i].size() );
    }

    int getId(int i, int v) {
        return upper_bound( vals[i].begin(), vals[i].end(), v ) - vals[i].begin() - 1;
    }

    void update(int x, int y, int v) {
        for(; x<=n; x+=x&-x)
            for(int p=getId(x, y); p<tree[x].size(); p+=p&-p) tree[x][p] += v;
    }

    ll Q(int x, int y) {
        if(x <= 0 || y <= 0) return 0;
        ll ans = 0;
        for(; x; x-=x&-x)
            for(int p=getId(x, y); p; p-=p&-p) ans += tree[x][p];
        return ans;
    }

    ll query(int x1, int y1, int x2, int y2) {
        if(x1 > x2 || y1 > y2) return 0;
        return Q(x2, y2) - Q(x1-1, y2) - Q(x2, y1-1) + Q(x1-1, y1-1);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<pii> v(n);
    set<int> s; s.insert(0);

    for(pii &x : v) {
        cin >> x.first >> x.second;
        s.insert(x.first);
        s.insert(x.second);
    }

    vector<array<int, 4> > qus(q);
    for(int i=0; i<q; i++) {
        cin >> qus[i][0] >> qus[i][1] >> qus[i][2];
        qus[i][3] = i;
        s.insert(qus[i][0]);
        s.insert(qus[i][1]);
        s.insert(qus[i][2]);
    }

    vector<int> comp(all(s));
    vector<pii> U;
    for(auto &x : v) U.push_back(x);

    BIT_2D_Offline bit(maxn, U);

    sort(qus.begin(), qus.end(), [&](array<int, 4> &a, array<int, 4> &b) {
        return a[2] > b[2];
    });

    sort(v.begin(), v.end(), [&](pii &a, pii &b) {
        return a.first + a.second > b.first + b.second;
    });

    vector<int> ans(q);

    int j=-1;
    for(auto &qu : qus) {
        while(j+1 < n && v[j+1].first + v[j+1].second >= qu[2]) {
            j++;
            bit.update(v[j].first, v[j].second, 1);
        }

        if(j > -1) ans[qu[3]] = bit.query(qu[0], qu[1], maxn, maxn);
    }

    for(int &x : ans) cout << x << '\n';
    return 0;
}

Compilation message

examination.cpp: In constructor 'BIT_2D_Offline::BIT_2D_Offline(int, std::vector<std::pair<int, int> >&)':
examination.cpp:25:31: warning: 'BIT_2D_Offline::vals' will be initialized after [-Wreorder]
   25 |     vector<vector<ll> > tree, vals;
      |                               ^~~~
examination.cpp:25:25: warning:   'std::vector<std::vector<long long int> > BIT_2D_Offline::tree' [-Wreorder]
   25 |     vector<vector<ll> > tree, vals;
      |                         ^~~~
examination.cpp:27:5: warning:   when initialized here [-Wreorder]
   27 |     BIT_2D_Offline(int n, vector<pii> &U) : n(n), vals(n+1), tree(n+1) {
      |     ^~~~~~~~~~~~~~
examination.cpp: In member function 'void BIT_2D_Offline::update(int, int, int)':
examination.cpp:44:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int p=getId(x, y); p<tree[x].size(); p+=p&-p) tree[x][p] += v;
      |                                    ~^~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Runtime error 10 ms 16476 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Runtime error 10 ms 16476 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -