Submission #255843

#	Time	Username	Problem	Language	Result	Execution time	Memory
255843		uacoder123	Examination (JOI19_examination)	C++14	43 / 100	3111 ms	250968 KiB

examination

    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) int(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
     
    typedef int lli;
    typedef pair <lli,lli> ii;
    typedef pair <lli,ii> iii;
    typedef vector <lli> vi;
    typedef tree<
    ii,
    null_type,
    less<ii>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;
     
    ordered_set segt[8*100000+1];
    lli n,q,co=1;
    void up(lli node,lli l,lli r,lli in,lli v)
    {
      segt[node].insert(mp(v,co));
      co++;
      lli m=(l+r)/2;
      if(l!=r)
      {
        if(in<=m)
          up(2*node+1,l,m,in,v);
        else
          up(2*node+2,m+1,r,in,v);
      }
    }
    lli query(lli node,lli l,lli r,lli s,lli e,lli v)
    {
      if(r<s||l>e)
        return(0);
      if(l>=s&&r<=e)
        return segt[node].size()-segt[node].order_of_key(mp(v,0));
      lli m=(l+r)/2;
      lli q1=query(2*node+1,l,m,s,e,v),q2=query(2*node+2,m+1,r,s,e,v);
      return(q1+q2);
    }
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cin>>n>>q;
      set<long long int> v,v1;
      unordered_map<long long int,lli> m,m1;
      ii s[n];
      pair<ii,long long int> qu[q];
      for(lli i=0;i<n;++i)
      {
        cin>>s[i].F>>s[i].S;
        v.insert(s[i].F);
        v1.insert(s[i].F*1LL+s[i].S);
      }
      for(lli i=0;i<q;++i)
      {
        cin>>qu[i].F.F>>qu[i].F.S>>qu[i].S;
        v.insert(qu[i].F.F);
        v1.insert(qu[i].S*1LL); 
      }
      auto it=v.begin();
      lli c=0,c1=0;
      auto it1=v1.begin();
      while(it1!=v1.end())
      {
        m1[(*it1)]=c1;
        c1++;
        it1++;
      }
      c=0;
      while(it!=v.end())
      {
        m[(*it)]=c;
        c++;
        it++;
      }
      vector<ii> st[c1];
      vector<iii> que[c1];
      for(lli i=0;i<n;++i)
      {
        lli su=s[i].F*1LL+s[i].S;
        s[i].F=m[s[i].F];
        st[m1[su]].pb(mp(s[i].F,s[i].S));
      }
      for(lli i=0;i<q;++i)
      {
        qu[i].F.F=m[qu[i].F.F];
        qu[i].S=m1[qu[i].S];
        que[qu[i].S].pb(mp(i,mp(qu[i].F.F,qu[i].F.S)));
      }
      lli ans[q]={};
      for(lli i=c1-1;i>=0;--i)
      {
        for(lli j=0;j<st[i].size();++j)
          up(0,0,c-1,st[i][j].F,st[i][j].S);
        for(lli j=0;j<que[i].size();++j)
          ans[que[i][j].F]=query(0,0,c-1,que[i][j].S.F,c-1,que[i][j].S.S);
      }
      for(lli i=0;i<q;++i)
        cout<<ans[i]<<'\n';
      return(0);
    }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(lli j=0;j<st[i].size();++j)
                     ~^~~~~~~~~~~~~
examination.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(lli j=0;j<que[i].size();++j)
                     ~^~~~~~~~~~~~~~

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