oj.uz

Submission #119209

# Submission time Handle Problem Language Result Execution time Memory
119209 2019-06-20T16:36:04 Z KLPP Examination (JOI19_examination) C++14
2 / 100
 3000 ms 751284 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;
  cin>>n>>q;
  pii arr[n];
  rep(i,0,n){
    cin>>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;
    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;
}

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 1024 KB Output is correct
7 Correct 301 ms 167544 KB Output is correct
8 Correct 304 ms 167516 KB Output is correct
9 Correct 302 ms 167800 KB Output is correct
10 Correct 212 ms 118476 KB Output is correct
11 Correct 203 ms 109860 KB Output is correct
12 Correct 31 ms 760 KB Output is correct
13 Correct 300 ms 167544 KB Output is correct
14 Correct 308 ms 167704 KB Output is correct
15 Correct 302 ms 167708 KB Output is correct
16 Correct 193 ms 108280 KB Output is correct
17 Correct 205 ms 117368 KB Output is correct
18 Correct 29 ms 632 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 751284 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 3063 ms 751284 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 1024 KB Output is correct
7 Correct 301 ms 167544 KB Output is correct
8 Correct 304 ms 167516 KB Output is correct
9 Correct 302 ms 167800 KB Output is correct
10 Correct 212 ms 118476 KB Output is correct
11 Correct 203 ms 109860 KB Output is correct
12 Correct 31 ms 760 KB Output is correct
13 Correct 300 ms 167544 KB Output is correct
14 Correct 308 ms 167704 KB Output is correct
15 Correct 302 ms 167708 KB Output is correct
16 Correct 193 ms 108280 KB Output is correct
17 Correct 205 ms 117368 KB Output is correct
18 Correct 29 ms 632 KB Output is correct
19 Execution timed out 3063 ms 751284 KB Time limit exceeded
20 Halted 0 ms 0 KB -