Submission #839475

#	Time	Username	Problem	Language	Result	Execution time	Memory
839475		vjudge1	Examination (JOI19_examination)	C++14	100 / 100	1252 ms	8140 KiB

examination

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
//#pragma expected_value
//#pragma isolated_call
//#pragma disjoint

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define setpre(i) setprecision(i)<<fixed
#define foru(i, a, b) for(int i=a;i<=b;++i)
#define ford(i, a, b) for(int i=a;i>=b;--i)
#define mp make_pair
#define moo cout<<"moo "
#define fi first
#define se second

ll lmod = 1e9 + 7;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int, int> ii;
typedef pair<double, double> dd;

struct query{
    int a, b, c, idx;
    query(int a, int b, int c, int idx): a(a), b(b), c(c), idx(idx){}
    const bool operator < (const query &q) const { return b > q.b; }
};

struct Fenwick{
    int n; vi bit;
    Fenwick(int n): n(n){
        bit.resize(n + 1);
    }
    void update(int idx, int diff){
        while(idx <= n){
            bit[idx] += diff;
            idx += idx & -idx;
        }
    }
    int sum(int idx){
        int ans = 0;
        while(idx >= 1){    
            ans += bit[idx];
            idx -= idx & -idx;
        }
        return ans;
    }
};

int s[100001], t[100001], sumpos[100001];
ii arrs[100001], arrt[100001];
int arrsum[100001];
vector<query> queries[1001];
int cnt[100001];
int ans[100001];

int main(){
	// freopen("input.inp", "r", stdin);
	// freopen("output.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    foru(i, 1, n){
        cin >> s[i] >> t[i];
        arrs[i] = mp(s[i], i);
        arrt[i] = mp(t[i], i);
        arrsum[i] = s[i] + t[i];
    }
    int sz = sqrt(n);
    sort(arrsum + 1, arrsum + n + 1);
    sort(arrs + 1, arrs + n + 1);
    sort(arrt + 1, arrt + n + 1);
    foru(i, 1, n){
        int z = lower_bound(arrsum + 1, arrsum + n + 1, s[i] + t[i]) - arrsum;
        sumpos[i] = z;
    }
    int maxblock = 0;
    foru(i, 1, q){
        int x, y, z; cin >> x >> y >> z;
        int a = lower_bound(arrs + 1, arrs + n + 1, mp(x, 0)) - arrs;
        int b = lower_bound(arrt + 1, arrt + n + 1, mp(y, 0)) - arrt;
        int c = lower_bound(arrsum + 1, arrsum + n + 1, z) - arrsum;
        queries[a / sz].pb(query(a, b, c, i));
        maxblock = max(maxblock, a / sz);
    }
    Fenwick f(n);
    memset(cnt, 0, sizeof cnt);
    int ptrl = n + 1, ptrr = n + 1;
    ford(i, maxblock, 0){
        sort(queries[i].begin(), queries[i].end());
        for(query que: queries[i]){
            
            int a = que.a, b = que.b, c = que.c, idx = que.idx;
            // moo << a << " " << b << " " << c << " " << idx << endl;
            while(ptrl > a){
                ptrl--;
                cnt[arrs[ptrl].se]++;
                if(cnt[arrs[ptrl].se] == 2){
                    f.update(sumpos[arrs[ptrl].se], 1);  
                    // cout << sumpos[arrs[ptrl].se] << " " << 1 << endl;
                } 
            }
            while(ptrl < a){
                cnt[arrs[ptrl].se]--;
                if(cnt[arrs[ptrl].se] == 1) {
                    f.update(sumpos[arrs[ptrl].se], -1);   
                    // cout << sumpos[arrs[ptrl].se] << " " << -1 << endl;
                }
                ptrl++;             
            }
            while(ptrr > b){
                ptrr--;
                cnt[arrt[ptrr].se]++;
                if(cnt[arrt[ptrr].se] == 2) {
                    f.update(sumpos[arrt[ptrr].se], 1);
                    // cout << sumpos[arrt[ptrr].se] << " " << 1 << endl;
                }
            }
            while(ptrr < b){
                cnt[arrt[ptrr].se]--;
                if(cnt[arrt[ptrr].se] == 1) {
                    f.update(sumpos[arrt[ptrr].se], -1);   
                    // cout << sumpos[arrt[ptrr].se] << " " << -1 << endl;
                }
                ptrr++;             
            }
            ans[idx] = f.sum(n) - f.sum(c - 1);
        }
    }
    foru(i, 1, q) cout << ans[i] << '\n';
    // foru(i, 1, n) cout << f.sum(i) - f.sum(i - 1) << " ";
    // cout << endl;
//	fclose(stdout);
}

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