oj.uz

Submission #255831

# Submission time Handle Problem Language Result Execution time Memory
255831 2020-08-01T23:18:08 Z uacoder123 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 368164 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[24*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;
  unordered_map<lli,lli> m;
  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);
    v.insert(s[i].S);
    v.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);
    v.insert(qu[i].F.S);
    v.insert(qu[i].S); 
  }
  auto it=v.begin();
  lli c=0,c1=0;
  while(it!=v.end())
  {
    m[(*it)]=c;
    c++;
    it++;
  }
  vector<ii> st[c];
  vector<iii> que[c];
  for(lli i=0;i<n;++i)
  {
    lli su=s[i].F+s[i].S;
    s[i].F=m[s[i].F];
    s[i].S=m[s[i].S];
    st[m[su]].pb(mp(s[i].F,s[i].S));
  }
  for(lli i=0;i<q;++i)
  {
    qu[i].F.S=m[qu[i].F.S];
    qu[i].F.F=m[qu[i].F.F];
    qu[i].S=m[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=c-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:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli j=0;j<st[i].size();++j)
                 ~^~~~~~~~~~~~~
examination.cpp:104:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli j=0;j<que[i].size();++j)
                 ~^~~~~~~~~~~~~~
examination.cpp:76:11: warning: unused variable 'c1' [-Wunused-variable]
   lli c=0,c1=0;
           ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 225784 KB Output is correct
2 Correct 199 ms 225784 KB Output is correct
3 Correct 194 ms 225784 KB Output is correct
4 Correct 200 ms 225784 KB Output is correct
5 Correct 190 ms 225784 KB Output is correct
6 Correct 193 ms 225784 KB Output is correct
7 Correct 228 ms 231416 KB Output is correct
8 Correct 228 ms 231416 KB Output is correct
9 Correct 226 ms 231416 KB Output is correct
10 Correct 221 ms 230464 KB Output is correct
11 Correct 240 ms 230520 KB Output is correct
12 Correct 209 ms 227320 KB Output is correct
13 Correct 237 ms 231048 KB Output is correct
14 Correct 235 ms 231088 KB Output is correct
15 Correct 230 ms 231032 KB Output is correct
16 Correct 221 ms 229496 KB Output is correct
17 Correct 218 ms 230008 KB Output is correct
18 Correct 210 ms 226560 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2871 ms 368136 KB Output is correct
2 Execution timed out 3038 ms 368164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2871 ms 368136 KB Output is correct
2 Execution timed out 3038 ms 368164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 225784 KB Output is correct
2 Correct 199 ms 225784 KB Output is correct
3 Correct 194 ms 225784 KB Output is correct
4 Correct 200 ms 225784 KB Output is correct
5 Correct 190 ms 225784 KB Output is correct
6 Correct 193 ms 225784 KB Output is correct
7 Correct 228 ms 231416 KB Output is correct
8 Correct 228 ms 231416 KB Output is correct
9 Correct 226 ms 231416 KB Output is correct
10 Correct 221 ms 230464 KB Output is correct
11 Correct 240 ms 230520 KB Output is correct
12 Correct 209 ms 227320 KB Output is correct
13 Correct 237 ms 231048 KB Output is correct
14 Correct 235 ms 231088 KB Output is correct
15 Correct 230 ms 231032 KB Output is correct
16 Correct 221 ms 229496 KB Output is correct
17 Correct 218 ms 230008 KB Output is correct
18 Correct 210 ms 226560 KB Output is correct
19 Correct 2871 ms 368136 KB Output is correct
20 Execution timed out 3038 ms 368164 KB Time limit exceeded
21 Halted 0 ms 0 KB -