Submission #444787

#	Time	Username	Problem	Language	Result	Execution time	Memory
444787		fcmalkcin	Examination (JOI19_examination)	C++17	100 / 100	1543 ms	87004 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937_64 rnd;

const ll maxn=1e5+10;
const ll mod =1e9+7 ;
const ll base=3e18;
/// you will be the best but now you just are trash
/// goal=0/7;

struct BIT_2D
{
    vector<ll> vt;
    vector<vector<ll>> f;
    vector<vector<ll>> node;
    void init(vector<ll> vt1)
    {
        vt=vt1;
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
        f=vector<vector<ll>> (vt.size()+2,vector<ll> (0) );
        node=vector<vector<ll>> (vt.size()+2,vector<ll>(0) );
    }
    void rearrange()
    {
        for (int i=1; i<=vt.size(); i++)
        {
            sort(node[i].begin(),node[i].end());
            node[i].resize(unique(node[i].begin(),node[i].end())-node[i].begin());
            f[i]=vector<ll> (node[i].size()+2,0);
        }
    }
    void fake_update(ll x,ll y)
    {
        for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i))
        {
            node[i].pb(y);
        }
    }
    void fake_get(ll x,ll y)
    {
        for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i; i-= i&(-i))
        {
            node[i].pb(y);
        }
    }
    void update(ll x,ll y,ll val)
    {
        for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i))
        {
            for (int j=lower_bound(node[i].begin(),node[i].end(),y)-node[i].begin()+1; j<=node[i].size(); j+= j&(-j))
            {
                f[i][j]=f[i][j]+val;
            }
        }
    }
    ll get(ll x,ll y)
    {
        ll ans=0;
        for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i; i-= i&(-i))
        {
            for (int j=lower_bound(node[i].begin(),node[i].end(),y)-node[i].begin()+1; j; j-= j&(-j))
            {
                ans+=f[i][j];
            }
        }
        return ans;
    }
} man;
pll a[maxn];

pair<pll,pll> c[maxn];
bool lf(pll a,pll b)
{
    return a.ff+a.ss<b.ff+b.ss;
}
bool lf1(pair<pll,pll> a,pair<pll,pll> b)
{
    return a.ss.ff<b.ss.ff;
}
ll ans[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, q;
    cin>> n>> q;
    vector<ll> vt;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i].ff>>a[i].ss;
        vt.pb(a[i].ff);
    }
    for (int i=1; i<=q; i++)
    {
        cin>>c[i].ff.ff>>c[i].ff.ss>>c[i].ss.ff;
        vt.pb(c[i].ff.ff-1);
        c[i].ss.ss=i;
    }
    vt.pb(base);
    man.init(vt);
    for (int i=1; i<=n; i++)
    {
        man.fake_update(a[i].ff,a[i].ss);
    }
    for (int i=1; i<=q; i++)
    {
        man.fake_get(c[i].ff.ff-1,c[i].ff.ss-1);
        man.fake_get(c[i].ff.ff-1,base);
        man.fake_get(base,c[i].ff.ss-1);
    }
    man.rearrange();
    sort(a+1,a+n+1,lf);
    sort(c+1,c+q+1,lf1);
    ll j=n;
    for (int i=q; i>=1; i--)
    {
        while (j>=1&&a[j].ff+a[j].ss>=c[i].ss.ff)
        {
            man.update(a[j].ff,a[j].ss,1);
            j--;
        }
        ll id=c[i].ss.ss;
        ans[id]=(n-j+man.get(c[i].ff.ff-1,c[i].ff.ss-1)-man.get(c[i].ff.ff-1,base)-man.get(base,c[i].ff.ss-1));
    }
  /*  for (int t=1; t<=j; t++)
        man.update(a[t].ff,a[t].ss,1);
    for (int i=q; i>=1; i--)
    {
        ll id=c[i].ss.ss;
        ans[id]+=(n+man.get(c[i].ff.ff-1,c[i].ff.ss-1)-man.get(c[i].ff.ff-1,base)-man.get(base,c[i].ff.ss-1));
    }*/
    for (int i=1; i<=q; i++)
        cout <<ans[i]<<endl;




}

Compilation message (stderr)

examination.cpp: In member function 'void BIT_2D::rearrange()':
examination.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i=1; i<=vt.size(); i++)
      |                       ~^~~~~~~~~~~
examination.cpp: In member function 'void BIT_2D::fake_update(long long int, long long int)':
examination.cpp:42:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i))
      |                                                                     ~^~~~~~~~~~~
examination.cpp: In member function 'void BIT_2D::update(long long int, long long int, long long int)':
examination.cpp:56:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i))
      |                                                                     ~^~~~~~~~~~~
examination.cpp:58:89: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j=lower_bound(node[i].begin(),node[i].end(),y)-node[i].begin()+1; j<=node[i].size(); j+= j&(-j))
      |                                                                                        ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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