oj.uz

Submission #201363

# Submission time Handle Problem Language Result Execution time Memory
201363 2020-02-10T10:21:30 Z Nordway Examination (JOI19_examination) C++14
100 / 100
 1787 ms 386660 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=1e5+11;
const int M=3e5+11;
const int W=1e3+11;
const int inf=1e9;
const ll INF=1e18;
const ll mod=1e9+7;
const ld EPS=1e-9;

struct st{
  int res=0;
  st *l=0,*r=0;
  int tl,tr;
  st(int a,int b){
    tl=a,tr=b;
  }
  void upd(int pos,int val){
    if(tl==tr){
      res+=val;
      return ;
    }
    int tm=(tl+tr)/2;
    if(pos<=tm){
      if(!l)l=new st(tl,tm);
      l->upd(pos,val);
    }
    else{
      if(!r)r=new st(tm+1,tr);
      r->upd(pos,val);
    }
    res=(l?l->res:0)+(r?r->res:0);
  }
  int get(int a,int b){
    if(tl>b||a>tr)return 0;
    if(a<=tl&&tr<=b)return res;
    return (l?l->get(a,b):0)+(r?r->get(a,b):0);
  }
};

struct bit{
  st *t[N];
  bit(){
    memset(t,0,sizeof(t));
  }
  void upd(int x,int y,int val){
    for(int i=x;i<N;i=(i|(i+1))){
      if(!t[i])t[i]=new st(1,N);
      t[i]->upd(y,val);
    }
  }
  int get(int x,int y){
    int res=0;
    for(int i=x;i>=0;i=(i&(i+1))-1){
      if(!t[i])continue;
      res+=t[i]->get(y,N-1);
    }
    return res;
  }
};

bit t;

pair<pair<int,int>,int>a[N],q[N];
int b[N],c[N];
int res[N];

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int n,Q;
  cin>>n>>Q;
  vector<int>x,y,z;
  for(int i=1;i<=n;i++){
    cin>>a[i].x.x>>a[i].x.y;
    a[i].y=i;
    x.pb(a[i].x.x);
    y.pb(a[i].x.y);
    z.pb(a[i].x.x+a[i].x.y);
  }
  sort(all(x));
  sort(all(y));
  sort(all(z));
  for(int i=1;i<=n;i++){
    b[i]=low_b(all(z),a[i].x.x+a[i].x.y)-z.begin()+1;
    a[i].x.x=low_b(all(x),a[i].x.x)-x.begin()+1;
    a[i].x.y=low_b(all(y),a[i].x.y)-y.begin()+1;
  }
  sort(a+1,a+n+1);
  for(int i=1;i<=Q;i++){
    cin>>q[i].x.x>>q[i].x.y>>c[i];
    q[i].x.x=low_b(all(x),q[i].x.x)-x.begin()+1;
    q[i].x.y=low_b(all(y),q[i].x.y)-y.begin()+1;
    c[i]=low_b(all(z),c[i])-z.begin()+1;
    q[i].y=i;
  }
  sort(q+1,q+Q+1);
  reverse(q+1,q+Q+1);
  int j=n;
  for(int i=1;i<=Q;i++){
    while(j&&a[j].x.x>=q[i].x.x)t.upd(a[j].x.y,b[a[j].y],1),j--;
    res[q[i].y]=t.get(N-1,c[q[i].y])-t.get(q[i].x.y-1,c[q[i].y]);
  }
  for(int i=1;i<=Q;i++){
    cout<<res[i]<<"\n";
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 5 ms 1144 KB Output is correct
5 Correct 5 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 29 ms 9592 KB Output is correct
8 Correct 29 ms 9592 KB Output is correct
9 Correct 31 ms 9592 KB Output is correct
10 Correct 20 ms 6904 KB Output is correct
11 Correct 21 ms 6776 KB Output is correct
12 Correct 13 ms 1784 KB Output is correct
13 Correct 25 ms 9592 KB Output is correct
14 Correct 28 ms 9592 KB Output is correct
15 Correct 28 ms 9592 KB Output is correct
16 Correct 19 ms 6776 KB Output is correct
17 Correct 19 ms 6008 KB Output is correct
18 Correct 11 ms 1400 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1787 ms 379044 KB Output is correct
2 Correct 1296 ms 381128 KB Output is correct
3 Correct 1296 ms 381412 KB Output is correct
4 Correct 524 ms 200036 KB Output is correct
5 Correct 578 ms 142180 KB Output is correct
6 Correct 196 ms 8256 KB Output is correct
7 Correct 1281 ms 381412 KB Output is correct
8 Correct 1152 ms 381284 KB Output is correct
9 Correct 1194 ms 380996 KB Output is correct
10 Correct 404 ms 129252 KB Output is correct
11 Correct 482 ms 127556 KB Output is correct
12 Correct 204 ms 7268 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1787 ms 379044 KB Output is correct
2 Correct 1296 ms 381128 KB Output is correct
3 Correct 1296 ms 381412 KB Output is correct
4 Correct 524 ms 200036 KB Output is correct
5 Correct 578 ms 142180 KB Output is correct
6 Correct 196 ms 8256 KB Output is correct
7 Correct 1281 ms 381412 KB Output is correct
8 Correct 1152 ms 381284 KB Output is correct
9 Correct 1194 ms 380996 KB Output is correct
10 Correct 404 ms 129252 KB Output is correct
11 Correct 482 ms 127556 KB Output is correct
12 Correct 204 ms 7268 KB Output is correct
13 Correct 1535 ms 381600 KB Output is correct
14 Correct 1431 ms 381368 KB Output is correct
15 Correct 1212 ms 381028 KB Output is correct
16 Correct 709 ms 204644 KB Output is correct
17 Correct 681 ms 142696 KB Output is correct
18 Correct 196 ms 8164 KB Output is correct
19 Correct 1538 ms 381904 KB Output is correct
20 Correct 1515 ms 381404 KB Output is correct
21 Correct 1624 ms 381024 KB Output is correct
22 Correct 391 ms 129252 KB Output is correct
23 Correct 456 ms 127332 KB Output is correct
24 Correct 196 ms 7268 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 5 ms 1144 KB Output is correct
5 Correct 5 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 29 ms 9592 KB Output is correct
8 Correct 29 ms 9592 KB Output is correct
9 Correct 31 ms 9592 KB Output is correct
10 Correct 20 ms 6904 KB Output is correct
11 Correct 21 ms 6776 KB Output is correct
12 Correct 13 ms 1784 KB Output is correct
13 Correct 25 ms 9592 KB Output is correct
14 Correct 28 ms 9592 KB Output is correct
15 Correct 28 ms 9592 KB Output is correct
16 Correct 19 ms 6776 KB Output is correct
17 Correct 19 ms 6008 KB Output is correct
18 Correct 11 ms 1400 KB Output is correct
19 Correct 1787 ms 379044 KB Output is correct
20 Correct 1296 ms 381128 KB Output is correct
21 Correct 1296 ms 381412 KB Output is correct
22 Correct 524 ms 200036 KB Output is correct
23 Correct 578 ms 142180 KB Output is correct
24 Correct 196 ms 8256 KB Output is correct
25 Correct 1281 ms 381412 KB Output is correct
26 Correct 1152 ms 381284 KB Output is correct
27 Correct 1194 ms 380996 KB Output is correct
28 Correct 404 ms 129252 KB Output is correct
29 Correct 482 ms 127556 KB Output is correct
30 Correct 204 ms 7268 KB Output is correct
31 Correct 1535 ms 381600 KB Output is correct
32 Correct 1431 ms 381368 KB Output is correct
33 Correct 1212 ms 381028 KB Output is correct
34 Correct 709 ms 204644 KB Output is correct
35 Correct 681 ms 142696 KB Output is correct
36 Correct 196 ms 8164 KB Output is correct
37 Correct 1538 ms 381904 KB Output is correct
38 Correct 1515 ms 381404 KB Output is correct
39 Correct 1624 ms 381024 KB Output is correct
40 Correct 391 ms 129252 KB Output is correct
41 Correct 456 ms 127332 KB Output is correct
42 Correct 196 ms 7268 KB Output is correct
43 Correct 1549 ms 386572 KB Output is correct
44 Correct 1585 ms 386592 KB Output is correct
45 Correct 1604 ms 386484 KB Output is correct
46 Correct 745 ms 195912 KB Output is correct
47 Correct 739 ms 165348 KB Output is correct
48 Correct 210 ms 7908 KB Output is correct
49 Correct 1718 ms 386440 KB Output is correct
50 Correct 1450 ms 386548 KB Output is correct
51 Correct 1609 ms 386660 KB Output is correct
52 Correct 524 ms 165212 KB Output is correct
53 Correct 470 ms 159076 KB Output is correct