oj.uz

Submission #255835

# Submission time Handle Problem Language Result Execution time Memory
255835 2020-08-01T23:32:04 Z uacoder123 Examination (JOI19_examination) C++14
22 / 100
 3000 ms 221132 KB 
#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 long long 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<lli> v,v1;
  unordered_map<lli,lli> m,m1;
  ii s[n];
  pair<ii,lli> 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+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); 
  }
  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+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]<<endl;
  return(0);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 75512 KB Output is correct
2 Correct 67 ms 75512 KB Output is correct
3 Correct 73 ms 75512 KB Output is correct
4 Correct 75 ms 75512 KB Output is correct
5 Correct 69 ms 75416 KB Output is correct
6 Correct 77 ms 75512 KB Output is correct
7 Correct 96 ms 79736 KB Output is correct
8 Correct 98 ms 79748 KB Output is correct
9 Correct 102 ms 79736 KB Output is correct
10 Correct 99 ms 79736 KB Output is correct
11 Correct 80 ms 77432 KB Output is correct
12 Correct 79 ms 76664 KB Output is correct
13 Correct 94 ms 79224 KB Output is correct
14 Correct 96 ms 79352 KB Output is correct
15 Correct 108 ms 79224 KB Output is correct
16 Correct 85 ms 76536 KB Output is correct
17 Correct 96 ms 79736 KB Output is correct
18 Correct 82 ms 76280 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2841 ms 213076 KB Output is correct
2 Correct 2606 ms 213120 KB Output is correct
3 Correct 2848 ms 213388 KB Output is correct
4 Correct 1859 ms 211936 KB Output is correct
5 Correct 711 ms 123008 KB Output is correct
6 Correct 635 ms 113380 KB Output is correct
7 Correct 2287 ms 208640 KB Output is correct
8 Correct 2718 ms 213036 KB Output is correct
9 Correct 2152 ms 208900 KB Output is correct
10 Correct 465 ms 106876 KB Output is correct
11 Correct 1486 ms 211584 KB Output is correct
12 Correct 525 ms 103132 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2841 ms 213076 KB Output is correct
2 Correct 2606 ms 213120 KB Output is correct
3 Correct 2848 ms 213388 KB Output is correct
4 Correct 1859 ms 211936 KB Output is correct
5 Correct 711 ms 123008 KB Output is correct
6 Correct 635 ms 113380 KB Output is correct
7 Correct 2287 ms 208640 KB Output is correct
8 Correct 2718 ms 213036 KB Output is correct
9 Correct 2152 ms 208900 KB Output is correct
10 Correct 465 ms 106876 KB Output is correct
11 Correct 1486 ms 211584 KB Output is correct
12 Correct 525 ms 103132 KB Output is correct
13 Correct 2832 ms 221132 KB Output is correct
14 Correct 2615 ms 219828 KB Output is correct
15 Correct 2553 ms 213012 KB Output is correct
16 Correct 1751 ms 215488 KB Output is correct
17 Correct 801 ms 126852 KB Output is correct
18 Correct 636 ms 113656 KB Output is correct
19 Correct 2375 ms 221072 KB Output is correct
20 Execution timed out 3079 ms 220212 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 75512 KB Output is correct
2 Correct 67 ms 75512 KB Output is correct
3 Correct 73 ms 75512 KB Output is correct
4 Correct 75 ms 75512 KB Output is correct
5 Correct 69 ms 75416 KB Output is correct
6 Correct 77 ms 75512 KB Output is correct
7 Correct 96 ms 79736 KB Output is correct
8 Correct 98 ms 79748 KB Output is correct
9 Correct 102 ms 79736 KB Output is correct
10 Correct 99 ms 79736 KB Output is correct
11 Correct 80 ms 77432 KB Output is correct
12 Correct 79 ms 76664 KB Output is correct
13 Correct 94 ms 79224 KB Output is correct
14 Correct 96 ms 79352 KB Output is correct
15 Correct 108 ms 79224 KB Output is correct
16 Correct 85 ms 76536 KB Output is correct
17 Correct 96 ms 79736 KB Output is correct
18 Correct 82 ms 76280 KB Output is correct
19 Correct 2841 ms 213076 KB Output is correct
20 Correct 2606 ms 213120 KB Output is correct
21 Correct 2848 ms 213388 KB Output is correct
22 Correct 1859 ms 211936 KB Output is correct
23 Correct 711 ms 123008 KB Output is correct
24 Correct 635 ms 113380 KB Output is correct
25 Correct 2287 ms 208640 KB Output is correct
26 Correct 2718 ms 213036 KB Output is correct
27 Correct 2152 ms 208900 KB Output is correct
28 Correct 465 ms 106876 KB Output is correct
29 Correct 1486 ms 211584 KB Output is correct
30 Correct 525 ms 103132 KB Output is correct
31 Correct 2832 ms 221132 KB Output is correct
32 Correct 2615 ms 219828 KB Output is correct
33 Correct 2553 ms 213012 KB Output is correct
34 Correct 1751 ms 215488 KB Output is correct
35 Correct 801 ms 126852 KB Output is correct
36 Correct 636 ms 113656 KB Output is correct
37 Correct 2375 ms 221072 KB Output is correct
38 Execution timed out 3079 ms 220212 KB Time limit exceeded
39 Halted 0 ms 0 KB -