oj.uz

Submission #119214

# Submission time Handle Problem Language Result Execution time Memory
119214 2019-06-20T16:41:21 Z KLPP Examination (JOI19_examination) C++14
2 / 100
 3000 ms 808088 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, lld x, lld y, lld pos, int val){
  if(pos<x || y<pos)return;
  n->val+=val;
  if(x==y){
    return;
  }
  extend(n);
  lld mid=(x+y)/2;
  update(n->l,x,mid,pos,val);
  update(n->r,mid+1,y,pos,val);
}
int Query(node *n, lld x, lld y,lld a, lld b){
  if(!n)return 0;
  if(y<a || b<x)return 0;
  if(a<=x && y<=b){
    return n->val;
  }
  lld 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, lld x, lld y,lld pos1, lld pos2, int val){
  if(pos1<x || y<pos1)return;
  update(n->tree,0,MAX,pos2,val);
  if(x==y)return;
  lld 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, lld x, lld y, lld X1, lld X2, lld Y1, lld 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);
  }
  lld 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){
    printf("%d\n",answer[i]);
  }
  /*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 282 ms 167684 KB Output is correct
8 Correct 283 ms 167480 KB Output is correct
9 Correct 282 ms 167584 KB Output is correct
10 Correct 198 ms 118396 KB Output is correct
11 Correct 184 ms 109932 KB Output is correct
12 Correct 25 ms 640 KB Output is correct
13 Correct 293 ms 167644 KB Output is correct
14 Correct 288 ms 167672 KB Output is correct
15 Correct 283 ms 167676 KB Output is correct
16 Correct 180 ms 108308 KB Output is correct
17 Correct 189 ms 117496 KB Output is correct
18 Correct 22 ms 512 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 808088 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 3067 ms 808088 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 282 ms 167684 KB Output is correct
8 Correct 283 ms 167480 KB Output is correct
9 Correct 282 ms 167584 KB Output is correct
10 Correct 198 ms 118396 KB Output is correct
11 Correct 184 ms 109932 KB Output is correct
12 Correct 25 ms 640 KB Output is correct
13 Correct 293 ms 167644 KB Output is correct
14 Correct 288 ms 167672 KB Output is correct
15 Correct 283 ms 167676 KB Output is correct
16 Correct 180 ms 108308 KB Output is correct
17 Correct 189 ms 117496 KB Output is correct
18 Correct 22 ms 512 KB Output is correct
19 Execution timed out 3067 ms 808088 KB Time limit exceeded
20 Halted 0 ms 0 KB -