oj.uz

Submission #444787

# Submission time Handle Problem Language Result Execution time Memory
444787 2021-07-15T09:49:35 Z fcmalkcin Examination (JOI19_examination) C++17
100 / 100
 1543 ms 87004 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 18 ms 2456 KB Output is correct
8 Correct 19 ms 2456 KB Output is correct
9 Correct 19 ms 2452 KB Output is correct
10 Correct 12 ms 1996 KB Output is correct
11 Correct 8 ms 972 KB Output is correct
12 Correct 5 ms 972 KB Output is correct
13 Correct 19 ms 2548 KB Output is correct
14 Correct 20 ms 2536 KB Output is correct
15 Correct 18 ms 2548 KB Output is correct
16 Correct 5 ms 844 KB Output is correct
17 Correct 10 ms 2132 KB Output is correct
18 Correct 3 ms 844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1255 ms 66036 KB Output is correct
2 Correct 1207 ms 65928 KB Output is correct
3 Correct 1317 ms 70464 KB Output is correct
4 Correct 508 ms 50248 KB Output is correct
5 Correct 309 ms 22520 KB Output is correct
6 Correct 140 ms 20612 KB Output is correct
7 Correct 829 ms 56344 KB Output is correct
8 Correct 1020 ms 62444 KB Output is correct
9 Correct 903 ms 58216 KB Output is correct
10 Correct 195 ms 16832 KB Output is correct
11 Correct 436 ms 50252 KB Output is correct
12 Correct 110 ms 17048 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1255 ms 66036 KB Output is correct
2 Correct 1207 ms 65928 KB Output is correct
3 Correct 1317 ms 70464 KB Output is correct
4 Correct 508 ms 50248 KB Output is correct
5 Correct 309 ms 22520 KB Output is correct
6 Correct 140 ms 20612 KB Output is correct
7 Correct 829 ms 56344 KB Output is correct
8 Correct 1020 ms 62444 KB Output is correct
9 Correct 903 ms 58216 KB Output is correct
10 Correct 195 ms 16832 KB Output is correct
11 Correct 436 ms 50252 KB Output is correct
12 Correct 110 ms 17048 KB Output is correct
13 Correct 1207 ms 64812 KB Output is correct
14 Correct 1203 ms 64844 KB Output is correct
15 Correct 1108 ms 63076 KB Output is correct
16 Correct 518 ms 51444 KB Output is correct
17 Correct 322 ms 23064 KB Output is correct
18 Correct 143 ms 20572 KB Output is correct
19 Correct 1319 ms 67664 KB Output is correct
20 Correct 1308 ms 66256 KB Output is correct
21 Correct 1314 ms 66652 KB Output is correct
22 Correct 198 ms 16924 KB Output is correct
23 Correct 427 ms 50924 KB Output is correct
24 Correct 115 ms 17180 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 18 ms 2456 KB Output is correct
8 Correct 19 ms 2456 KB Output is correct
9 Correct 19 ms 2452 KB Output is correct
10 Correct 12 ms 1996 KB Output is correct
11 Correct 8 ms 972 KB Output is correct
12 Correct 5 ms 972 KB Output is correct
13 Correct 19 ms 2548 KB Output is correct
14 Correct 20 ms 2536 KB Output is correct
15 Correct 18 ms 2548 KB Output is correct
16 Correct 5 ms 844 KB Output is correct
17 Correct 10 ms 2132 KB Output is correct
18 Correct 3 ms 844 KB Output is correct
19 Correct 1255 ms 66036 KB Output is correct
20 Correct 1207 ms 65928 KB Output is correct
21 Correct 1317 ms 70464 KB Output is correct
22 Correct 508 ms 50248 KB Output is correct
23 Correct 309 ms 22520 KB Output is correct
24 Correct 140 ms 20612 KB Output is correct
25 Correct 829 ms 56344 KB Output is correct
26 Correct 1020 ms 62444 KB Output is correct
27 Correct 903 ms 58216 KB Output is correct
28 Correct 195 ms 16832 KB Output is correct
29 Correct 436 ms 50252 KB Output is correct
30 Correct 110 ms 17048 KB Output is correct
31 Correct 1207 ms 64812 KB Output is correct
32 Correct 1203 ms 64844 KB Output is correct
33 Correct 1108 ms 63076 KB Output is correct
34 Correct 518 ms 51444 KB Output is correct
35 Correct 322 ms 23064 KB Output is correct
36 Correct 143 ms 20572 KB Output is correct
37 Correct 1319 ms 67664 KB Output is correct
38 Correct 1308 ms 66256 KB Output is correct
39 Correct 1314 ms 66652 KB Output is correct
40 Correct 198 ms 16924 KB Output is correct
41 Correct 427 ms 50924 KB Output is correct
42 Correct 115 ms 17180 KB Output is correct
43 Correct 1543 ms 84776 KB Output is correct
44 Correct 1538 ms 87004 KB Output is correct
45 Correct 1516 ms 86992 KB Output is correct
46 Correct 692 ms 67996 KB Output is correct
47 Correct 361 ms 25988 KB Output is correct
48 Correct 141 ms 20696 KB Output is correct
49 Correct 1376 ms 83096 KB Output is correct
50 Correct 1471 ms 85400 KB Output is correct
51 Correct 1240 ms 77848 KB Output is correct
52 Correct 223 ms 19504 KB Output is correct
53 Correct 522 ms 65104 KB Output is correct