제출 #1206003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206003		minhpk	Examination (JOI19_examination)	C++20	100 / 100	1132 ms	17120 KiB

examination

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
struct node{
     int x,y,t,r;
};
bool cmp(node a,node b){
    return a.x<b.x;
}
node z[1000005];

int val[1000005];
int rank1[1000005];

struct node1{
      int type,x,y,t,r,id;
};
vector <node1> v;

bool cmp1(node1 a,node1 b){
    if (a.t==b.t){
        return a.type<b.type;
    }
    return a.t>b.t;
}
const int maxn=1e5;
const int block=320;
vector <int> cnt[maxn/block +5LL];
int res[1000005];

void preprocess(){
    for (int i=1;i<=a;i++){
         cnt[i/block].push_back(-1);
         val[i]=-1;
    }
}
int getpos(int n){
   int l=1;
   int r=a;
   int pos=a+1;
   while (l<=r){
        int mid=(l+r)/2;
        if (rank1[mid]>=n){
            pos=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
   }
   return pos;
}

void update(int pos,int val){
    auto pos1 = lower_bound(cnt[pos / block].begin(), cnt[pos / block].end(), -1);
    cnt[pos / block].erase(pos1);
    cnt[pos / block].insert(upper_bound(cnt[pos / block].begin(), cnt[pos / block].end(), val), val);
}


int get(int l, int r, int val1) {
    if (l>r){
        return 0;
    }
    int sum = 0;
    int blockl = l / block;
    int blockr = r / block;

    if (blockl == blockr) {
        for (int i = l; i <= r; i++) {
            sum += (val[i] >= val1);
        }
    } else {
        for (int i = l, lim = (blockl + 1) * block; i < lim; i++) {
            sum += (val[i] >= val1);
        }
        for (int i = r; i >= blockr * block; i--) {
            sum += (val[i] >= val1);
        }
        for (int i = blockl + 1; i <= blockr - 1; i++) {
            int pre= lower_bound(cnt[i].begin(),cnt[i].end(),val1)-cnt[i].begin();
            if (pre<cnt[i].size()){
                int pre1=cnt[i].size()-pre;
                sum+=pre1;
            }
        }
    }
    return sum;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i].x >> z[i].y;
         z[i].t=z[i].x+z[i].y;
    }

    sort(z+1,z+1+a,cmp);
    for (int i=1;i<=a;i++){
         z[i].r=i;
         rank1[i]=z[i].x;
         v.push_back({1,z[i].x,z[i].y,z[i].t,z[i].r,0});
    }


    for (int i=1;i<=b;i++){
         int x,y,t;
         cin >> x >> y >> t;
         v.push_back({2,x,y,t,0,i});
    }

    sort(v.begin(),v.end(),cmp1);

    preprocess();
    for (auto p:v){
        int type=p.type;
        int x=p.x;
        int y=p.y;
        int r=p.r;
        int id=p.id;
        if (type==1){
            val[r]=y;
            update(r,y);
        }else{
            int l=getpos(x);
            res[id]=get(l,a,y);
        }
    }
    for (int i=1;i<=b;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57