Submission #105122

#	Time	Username	Problem	Language	Result	Execution time	Memory
105122		reality	Examination (JOI19_examination)	C++17	100 / 100	1104 ms	88680 KiB

examination

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e5 + 5;
const int oo = 1e9;
int a[N];
int b[N];
int c[N];
int d[N];
int e[N];
void Upd(int &x) {
	x = oo - x;
}
vi V[N * 5];
vi T[N * 5];
vi Q[N * 5];
vi R[N * 5];
int answer[N];
int main(void) {
    int n,q;
    ios_base :: sync_with_stdio(0);
    vi w,W;
    cin>>n>>q;
    for (int i = 1;i <= n;++i)
    	cin>>a[i]>>b[i],Upd(a[i]),Upd(b[i]),w.pb(a[i]),w.pb(b[i]),W.pb(a[i] + b[i]);
    for (int i = 1;i <= q;++i)
    	cin>>c[i]>>d[i]>>e[i],e[i] = 2 * oo - e[i],Upd(c[i]),Upd(d[i]),w.pb(c[i]),w.pb(d[i]),W.pb(e[i]);
    sort(all(w));
    sort(all(W));
    w.resize(unique(all(w)) - w.begin());
    W.resize(unique(all(W)) - W.begin());
    for (int i = 1;i <= n;++i) {
    	R[lower_bound(all(W),a[i] + b[i]) - W.begin() + 1].pb(i);
    	a[i] = lower_bound(all(w),a[i]) - w.begin() + 1;
    	b[i] = lower_bound(all(w),b[i]) - w.begin() + 1;
    }
    for (int i = 1;i <= q;++i) {
    	c[i] = lower_bound(all(w),c[i]) - w.begin() + 1;
    	d[i] = lower_bound(all(w),d[i]) - w.begin() + 1;
    	e[i] = lower_bound(all(W),e[i]) - W.begin() + 1;
    	Q[e[i]].pb(i);
    }
    const int SZ1 = w.size();
    const int SZ2 = W.size();
    for (int i = 1;i <= n;++i) {
    	for (int j = a[i];j <= SZ1;j += j&(-j))
    		V[j].pb(b[i]);
    }
    for (int i = 1;i <= SZ1;++i) {
    	sort(all(V[i]));
    	V[i].resize(unique(all(V[i])) - V[i].begin());
    	T[i].resize(V[i].size() + 4);
    }
    auto upd = [&](int x,int y) {
    	for (int i = x;i <= SZ1;i += i&(-i)) {
    		const int sz = V[i].size();
    		for (int j = lower_bound(all(V[i]),y) - V[i].begin() + 1;j <= sz;j += j&(-j))
    			T[i][j] += 1;
    	}
    };
    auto query = [&](int x,int y) {
    	int ans = 0;
    	for (int i = x;i;i -= i&(-i)) {
    		const int sz = V[i].size();
    		for (int j = lower_bound(all(V[i]),y + 1) - V[i].begin();j;j -= j&(-j))
    			ans += T[i][j];
    	}
    	return ans;
    };
    for (int i = 1;i <= SZ2;++i) {
    	for (auto it : R[i])
    		upd(a[it],b[it]);
    	for (auto it : Q[i])
    		answer[it] = query(c[it],d[it]);
    }
    for (int i = 1;i <= q;++i)
    	cout << answer[i] << '\n';
    return 0;
}

Compilation message (stderr)

examination.cpp: In lambda function:
examination.cpp:79:17: warning: unused variable 'sz' [-Wunused-variable]
       const int sz = V[i].size();
                 ^~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57