oj.uz

Submission #348273

# Submission time Handle Problem Language Result Execution time Memory
348273 2021-01-14T13:16:29 Z uacoder123 Examination (JOI19_examination) C++14
43 / 100
 3000 ms 248080 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 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

examination.cpp: In function 'int main()':
examination.cpp:109:11: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(;j<quer[m1[sums[i]]].size();++j)
      |          ~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:116:11: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(;j<quer[m1[sums[i]]].size();++j)
      |          ~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 75500 KB Output is correct
2 Correct 68 ms 75500 KB Output is correct
3 Correct 69 ms 75500 KB Output is correct
4 Correct 73 ms 75528 KB Output is correct
5 Correct 69 ms 75500 KB Output is correct
6 Correct 68 ms 75500 KB Output is correct
7 Correct 92 ms 79724 KB Output is correct
8 Correct 100 ms 79852 KB Output is correct
9 Correct 93 ms 79852 KB Output is correct
10 Correct 93 ms 79724 KB Output is correct
11 Correct 85 ms 77436 KB Output is correct
12 Correct 78 ms 76652 KB Output is correct
13 Correct 93 ms 79340 KB Output is correct
14 Correct 94 ms 79468 KB Output is correct
15 Correct 93 ms 79340 KB Output is correct
16 Correct 75 ms 76524 KB Output is correct
17 Correct 110 ms 79724 KB Output is correct
18 Correct 75 ms 76268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2540 ms 211168 KB Output is correct
2 Correct 2564 ms 211220 KB Output is correct
3 Correct 2681 ms 211120 KB Output is correct
4 Correct 1712 ms 209000 KB Output is correct
5 Correct 625 ms 120196 KB Output is correct
6 Correct 461 ms 111008 KB Output is correct
7 Correct 2428 ms 206828 KB Output is correct
8 Correct 2393 ms 210992 KB Output is correct
9 Correct 2080 ms 206600 KB Output is correct
10 Correct 321 ms 104000 KB Output is correct
11 Correct 1407 ms 208868 KB Output is correct
12 Correct 386 ms 100704 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2540 ms 211168 KB Output is correct
2 Correct 2564 ms 211220 KB Output is correct
3 Correct 2681 ms 211120 KB Output is correct
4 Correct 1712 ms 209000 KB Output is correct
5 Correct 625 ms 120196 KB Output is correct
6 Correct 461 ms 111008 KB Output is correct
7 Correct 2428 ms 206828 KB Output is correct
8 Correct 2393 ms 210992 KB Output is correct
9 Correct 2080 ms 206600 KB Output is correct
10 Correct 321 ms 104000 KB Output is correct
11 Correct 1407 ms 208868 KB Output is correct
12 Correct 386 ms 100704 KB Output is correct
13 Correct 2467 ms 217536 KB Output is correct
14 Correct 2741 ms 216328 KB Output is correct
15 Correct 2516 ms 210952 KB Output is correct
16 Correct 1676 ms 212288 KB Output is correct
17 Correct 691 ms 123456 KB Output is correct
18 Correct 457 ms 110820 KB Output is correct
19 Correct 2529 ms 217436 KB Output is correct
20 Correct 2587 ms 216896 KB Output is correct
21 Correct 2495 ms 216244 KB Output is correct
22 Correct 321 ms 104044 KB Output is correct
23 Correct 1404 ms 208748 KB Output is correct
24 Correct 383 ms 100576 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 75500 KB Output is correct
2 Correct 68 ms 75500 KB Output is correct
3 Correct 69 ms 75500 KB Output is correct
4 Correct 73 ms 75528 KB Output is correct
5 Correct 69 ms 75500 KB Output is correct
6 Correct 68 ms 75500 KB Output is correct
7 Correct 92 ms 79724 KB Output is correct
8 Correct 100 ms 79852 KB Output is correct
9 Correct 93 ms 79852 KB Output is correct
10 Correct 93 ms 79724 KB Output is correct
11 Correct 85 ms 77436 KB Output is correct
12 Correct 78 ms 76652 KB Output is correct
13 Correct 93 ms 79340 KB Output is correct
14 Correct 94 ms 79468 KB Output is correct
15 Correct 93 ms 79340 KB Output is correct
16 Correct 75 ms 76524 KB Output is correct
17 Correct 110 ms 79724 KB Output is correct
18 Correct 75 ms 76268 KB Output is correct
19 Correct 2540 ms 211168 KB Output is correct
20 Correct 2564 ms 211220 KB Output is correct
21 Correct 2681 ms 211120 KB Output is correct
22 Correct 1712 ms 209000 KB Output is correct
23 Correct 625 ms 120196 KB Output is correct
24 Correct 461 ms 111008 KB Output is correct
25 Correct 2428 ms 206828 KB Output is correct
26 Correct 2393 ms 210992 KB Output is correct
27 Correct 2080 ms 206600 KB Output is correct
28 Correct 321 ms 104000 KB Output is correct
29 Correct 1407 ms 208868 KB Output is correct
30 Correct 386 ms 100704 KB Output is correct
31 Correct 2467 ms 217536 KB Output is correct
32 Correct 2741 ms 216328 KB Output is correct
33 Correct 2516 ms 210952 KB Output is correct
34 Correct 1676 ms 212288 KB Output is correct
35 Correct 691 ms 123456 KB Output is correct
36 Correct 457 ms 110820 KB Output is correct
37 Correct 2529 ms 217436 KB Output is correct
38 Correct 2587 ms 216896 KB Output is correct
39 Correct 2495 ms 216244 KB Output is correct
40 Correct 321 ms 104044 KB Output is correct
41 Correct 1404 ms 208748 KB Output is correct
42 Correct 383 ms 100576 KB Output is correct
43 Correct 2970 ms 248080 KB Output is correct
44 Correct 2971 ms 247896 KB Output is correct
45 Execution timed out 3076 ms 247964 KB Time limit exceeded
46 Halted 0 ms 0 KB -