제출 #119211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119211		KLPP	Examination (JOI19_examination)	C++14	2 / 100	3095 ms	783776 KiB

examination

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57