Submission #1290938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290938		maxphast	Examination (JOI19_examination)	C++20	100 / 100	450 ms	18480 KiB

examination

/*
* @Author: MaxPhast
* @File:   test.cpp
* @Date:   2025-11-14 20:38:12
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair <int , int>
#define iii pair <int , ii>
#define iiii pair <ii , ii>
#define FOR(i , l , r) for(int i = (l) , _r = (r) ; i <= _r ; ++ i)
#define FORD(i , r , l) for(int i = (r) , _l = (l) ; i >= _l ; -- i)
#define ALL(vec) vec.begin() , vec.end()
#define UNI(vec) sort(ALL(vec)) , vec.erase(unique(ALL(vec)) , vec.end())
#define pb push_back
#define MASK(i) (1ll << i)
#define BIT(mask , i) ((mask >> i) & 1ll)
#define ON(mask , i) (mask | MASK(i))
#define OFF(mask , i) (mask & (~MASK(i)))
#define TURN(mask , i) (mask ^ MASK(i))
#define BP(mask) __builtin_popcountll(mask)
#define sqr(x) (1ll * (x) * (x))
#define fi first
#define se second
#define oo 1e18
#define time() cerr << " \n " << "Time : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms."
#define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);}

template <class X , class Y>
    bool maxz(X &a , const Y b)
    {
        if(a < b)
        {
            a = b;
            return true;
        }
        return false;
    }
template <class X , class Y>
    bool minz(X &a , const Y b)
    {
        if(a > b)
        {
            a = b;
            return true;
        }
        return false;
    }

namespace MaxPhast
{

    const int N = 2e5 + 5;

    int n , q;
    int bit[N] , ans[N];
    iiii query[N];
    vector <int> ids;

    int lower(int x)
    {
        return lower_bound(ALL(ids) , x) - ids.begin() + 1;
    }

    void up(int pos , int val)
    {
        for(int i = pos ; i ; i -= i & -i)
            bit[i] += val;
    }

    int get(int pos)
    {
        int res = 0;
        for(int i = pos ; i <= ids.size() ; i += i & -i)
            res += bit[i];
        return res;
    }

    void DNC(int l , int r)
    {
        if(l == r) return;
        int mid = l + r >> 1;

        vector <iii> left , right;
        
        FOR(i , l , mid)
            if(query[i].se.se == 0)
                left.pb({query[i].fi.se , query[i].se});

        FOR(i , mid + 1 , r)
            if(query[i].se.se < 0)
                right.pb({query[i].fi.se , query[i].se});

        sort(ALL(left) , greater <iii>());
        sort(ALL(right) , greater <iii>());

        int j = 0;

        FOR(i , 0 , right.size() - 1)
        {
            while(j < left.size() && right[i].fi <= left[j].fi)
            {
                up(lower(left[j].se.fi) , 1);
                j ++;
            }

            ans[-right[i].se.se] += get(lower(right[i].se.fi));
        }

        while(j--)
            up(lower(left[j].se.fi) , -1);

        DNC(l , mid);
        DNC(mid + 1 , r);
    }

    void solve()
    {
        cin >> n >> q;

        FOR(i , 1 , n)
        {
            int s , t; cin >> s >> t;
            query[i] = {{s + t , s} , {t , 0}};
            ids.pb(t);
        }

        FOR(i , n + 1 , n + q)
        {
            int a , b , c; cin >> a >> b >> c;
            query[i] = {{c , a} , {b , - i}};
            ids.pb(b);
        }

        sort(query + 1 , query + 1 + n + q , greater <iiii>());
        UNI(ids);

        DNC(1 , n + q);

        FOR(i , n + 1 , n + q)
            cout << ans[i] << "\n";
    }

}

signed main()
{
    ios_base :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
    IO(test);
    MaxPhast :: solve();
    time();
}
/*

*/

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:29:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:151:5: note: in expansion of macro 'IO'
  151 |     IO(test);
      |     ^~
examination.cpp:29:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);}
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:151:5: note: in expansion of macro 'IO'
  151 |     IO(test);
      |     ^~

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