Submission #258913

#	Time	Username	Problem	Language	Result	Execution time	Memory
258913		uacoder123	Examination (JOI19_examination)	C++14	100 / 100	2915 ms	247456 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;
          while(it!=v.end())
          {
            m[(*it)]=c;
            c++;
            it++;
          }
          vector<vector<iii>> quer;
          vi sums;
          for(lli i=0;i<n;++i)
          {
            lli su=s[i].F*1LL+s[i].S;
            s[i].F=m[s[i].F];
            if(m1.find(su)==m1.end())
            {
              m1[su]=quer.size();
              quer.pb(vector<iii>(0));
              sums.pb(su);              
            }
            quer[m1[su]].pb(mp(-1,mp(s[i].F,s[i].S)));
          }
          for(lli i=0;i<q;++i)
          {
            qu[i].F.F=m[qu[i].F.F];
            if(m1.find(qu[i].S)==m1.end())
            {
              m1[qu[i].S]=quer.size();
              quer.pb(vector<iii>(0));
              sums.pb(qu[i].S);              
            }
            quer[m1[qu[i].S]].pb(mp(i,mp(qu[i].F.F,qu[i].F.S)));  
          }
          sort(all(sums));
          lli ans[q]={};
          for(lli i=sums.size()-1;i>=0;--i)
          {
            lli j=0;
            for(;j<quer[m1[sums[i]]].size();++j)
            {
              if(quer[m1[sums[i]]][j].F==-1)
                up(0,0,c-1,quer[m1[sums[i]]][j].S.F,quer[m1[sums[i]]][j].S.S);
              else
                break;
          }
            for(;j<quer[m1[sums[i]]].size();++j)
              ans[quer[m1[sums[i]]][j].F]=query(0,0,c-1,quer[m1[sums[i]]][j].S.F,c-1,quer[m1[sums[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:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;j<quer[m1[sums[i]]].size();++j)
                  ~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;j<quer[m1[sums[i]]].size();++j)
                  ~^~~~~~~~~~~~~~~~~~~~~~~~~

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