oj.uz

Submission #119211

# Submission time Handle Problem Language Result Execution time Memory
119211 2019-06-20T16:38:48 Z KLPP Examination (JOI19_examination) C++14
2 / 100
 3000 ms 783776 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define MAX 1000000000
struct query{
  lld A,B,C;
  int index;
};
bool operator<(query a, query b){
  if(a.C<b.C)return true;
  return false;
}
class FT{
  int arr[200000];
  int n;
public:
  void init(int N){
    n=N;
    rep(i,0,n)arr[i]=0;
  }
  void update(int pos, int val){
    for(int i=pos;i<=n;i+=(i&(-i))){
      arr[i]+=val;
    }
  }
  int query(int pos){
    int ans=0;
    for(int i=pos;i>0;i-=(i&(-i))){
      ans+=arr[i];
    }
    return ans;
  }
};
/*class ANS{
  FT *F;
  set<lld> values;
  vector<lld> v;
public:
  void insert(lld val){
    values.insert(val);
  }
  void compress(){
    trav(a,values){
      v.push_back(a);
    }
    F->init(values.size());
  }
  int find(lld val){
    int lo=0;
    int hi=v.size()-1;
    while(hi>lo){
      int mid=(hi+lo)/2;
      if(v[mid]==val)return mid;
      if(v[mid]>val)hi=mid-1;
      else lo=mid+1;
    }
    return lo;
  }
  void student(lld A,lld B){
    
  }
  };*/
struct node{
  int val;
  node *l,*r;
};
void extend(node *n){
  if(!n->l){
    n->l=new node();
    n->r=new node();
    n->l->val=0;
    n->r->val=0;
  }
}
void update(node *n, int x, int y, int pos, int val){
  if(pos<x || y<pos)return;
  n->val+=val;
  if(x==y){
    return;
  }
  extend(n);
  int mid=(x+y)/2;
  update(n->l,x,mid,pos,val);
  update(n->r,mid+1,y,pos,val);
}
int Query(node *n, int x, int y,int a, int b){
  if(!n)return 0;
  if(y<a || b<x)return 0;
  if(a<=x && y<=b){
    return n->val;
  }
  int mid=(x+y)/2;
  return Query(n->l,x,mid,a,b)+Query(n->r,mid+1,y,a,b);
}
struct node2{
  node *tree;
  node2 *l,*r;
};
void extend(node2 *n){
  if(!n->l){
    n->l=new node2();
    n->r=new node2();
    n->l->tree=new node();
    n->r->tree=new node();
    n->l->tree->val=0;
    n->r->tree->val=0;
  }
}
void update(node2 *n, int x, int y,int pos1, int pos2, int val){
  if(pos1<x || y<pos1)return;
  update(n->tree,0,MAX,pos2,val);
  if(x==y)return;
  int mid=(x+y)/2;
  extend(n);
  update(n->l,x,mid,pos1,pos2,val);
  update(n->r,mid+1,y,pos1,pos2,val);
}
int Query(node2 *n, int x, int y, int X1, int X2, int Y1, int Y2){
  if(!n)return 0;
  if(X2<x || y<X1)return 0;
  if(X1<=x && y<=X2){
    return Query(n->tree,0,MAX,Y1,Y2);
  }
  int mid=(x+y)/2;
  return Query(n->l,x,mid,X1,X2,Y1,Y2)+Query(n->r,mid+1,y,X1,X2,Y1,Y2);
}
int main(){
  node2 *ST;
  ST=new node2();
  ST->tree=new node();
  ST->tree->val=0;
  int n,q;
  scanf("%d %d",&n,&q);
  pii arr[n];
  rep(i,0,n){
    scanf("%lld %lld",&arr[i].first,&arr[i].second);
    arr[i].first+=arr[i].second;
  }
  sort(arr,arr+n);
  rep(i,0,n){
    arr[i].first-=arr[i].second;
  }
  query Q[q];
  rep(i,0,q){
    //cin>>Q[i].A>>Q[i].B>>Q[i].C;
    scanf("%lld %lld %lld",&Q[i].A,&Q[i].B,&Q[i].C);
    Q[i].index=i;
  }
  sort(Q,Q+q);
  reverse(Q,Q+q);
  int answer[q];
  int ptr=n-1;
  rep(i,0,q){
    while(ptr>=0 && arr[ptr].first+arr[ptr].second>=Q[i].C){
      update(ST,0,MAX,arr[ptr].first,arr[ptr].second,1);
      ptr--;
    }
    answer[Q[i].index]=Query(ST,0,MAX,Q[i].A,MAX,Q[i].B,MAX);
  }
  rep(i,0,q){
    cout<<answer[i]<<endl;
  }
  /*update(n,0,MAX,1,1,1);
  cout<<Query(n,0,MAX,1,3,0,1)<<endl;*/
  return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&q);
   ~~~~~^~~~~~~~~~~~~~~
examination.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&arr[i].first,&arr[i].second);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld",&Q[i].A,&Q[i].B,&Q[i].C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 290 ms 167644 KB Output is correct
8 Correct 297 ms 167544 KB Output is correct
9 Correct 294 ms 167704 KB Output is correct
10 Correct 197 ms 118528 KB Output is correct
11 Correct 189 ms 109816 KB Output is correct
12 Correct 28 ms 612 KB Output is correct
13 Correct 296 ms 167644 KB Output is correct
14 Correct 286 ms 167668 KB Output is correct
15 Correct 283 ms 167548 KB Output is correct
16 Correct 182 ms 108284 KB Output is correct
17 Correct 195 ms 117500 KB Output is correct
18 Correct 30 ms 512 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3095 ms 783776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3095 ms 783776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 290 ms 167644 KB Output is correct
8 Correct 297 ms 167544 KB Output is correct
9 Correct 294 ms 167704 KB Output is correct
10 Correct 197 ms 118528 KB Output is correct
11 Correct 189 ms 109816 KB Output is correct
12 Correct 28 ms 612 KB Output is correct
13 Correct 296 ms 167644 KB Output is correct
14 Correct 286 ms 167668 KB Output is correct
15 Correct 283 ms 167548 KB Output is correct
16 Correct 182 ms 108284 KB Output is correct
17 Correct 195 ms 117500 KB Output is correct
18 Correct 30 ms 512 KB Output is correct
19 Execution timed out 3095 ms 783776 KB Time limit exceeded
20 Halted 0 ms 0 KB -