Submission #998643

#	Time	Username	Problem	Language	Result	Execution time	Memory
998643		VMaksimoski008	Examination (JOI19_examination)	C++17	100 / 100	715 ms	96108 KiB

examination

#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<int> > 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( -1 );

		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;
	}

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

	int 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;
        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][0]++; qus[i][1]++; qus[i][2] += 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) {
        x.first = lower_bound(comp.begin(), comp.end(), x.first) - comp.begin();
        x.second = lower_bound(comp.begin(), comp.end(), x.second) - comp.begin();
        U.push_back(x);
    }

    for(auto &x : qus) {
        x[0] = lower_bound(comp.begin(), comp.end(), x[0]) - comp.begin();
        x[1] = lower_bound(comp.begin(), comp.end(), x[1]) - comp.begin();
        x[2] = lower_bound(comp.begin(), comp.end(), x[2]) - comp.begin();
    }

    BIT_2D_Offline bit(5*n+5, 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 comp[a.first] + comp[a.second] > comp[b.first] + comp[b.second];
    });

    vector<int> ans(q);

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

        //cout << "! " << qu[0] << " " << qu[1] << '\n';
        ans[qu[3]] = bit.query(qu[0], qu[1], 5*n, 5*n);
    }

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

Compilation message (stderr)

examination.cpp: In constructor 'BIT_2D_Offline::BIT_2D_Offline(int, std::vector<std::pair<int, int> >&)':
examination.cpp:25:29: warning: 'BIT_2D_Offline::vals' will be initialized after [-Wreorder]
   25 |  vector<vector<int> > tree, vals;
      |                             ^~~~
examination.cpp:25:23: warning:   'std::vector<std::vector<int> > BIT_2D_Offline::tree' [-Wreorder]
   25 |  vector<vector<int> > tree, vals;
      |                       ^~~~
examination.cpp:27:2: 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:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57