제출 #636588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636588		Ronin13	Examination (JOI19_examination)	C++14	100 / 100	412 ms	49512 KiB

examination

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 1e5 + 1;
int a[NMAX], b[NMAX];
vector <vector <int> > t[2];

void build(int v, int l, int r){
    if(l == r){
        t[0][v].pb(a[l]);
        t[1][v].pb(b[l]);
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    for(int i = 0; i < 2; i++){
        t[i][v].resize(t[i][2 * v].size() + t[i][2 * v + 1].size());
        merge(t[i][2 * v].begin(), t[i][2 * v].end(), t[i][2 * v + 1].begin(), t[i][2 * v + 1].end(), t[i][v].begin());
    }
}

int get(int v, int l, int r, int st, int fin, int ind, int val){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin){
        return (int)(t[ind][v].end() - lower_bound(t[ind][v].begin(), t[ind][v].end(), val));
    }
    int m = (l + r) / 2;
    return get(2 * v, l, m, st, fin, ind, val) + get(2 * v + 1, m + 1, r, st, fin, ind, val);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    vector <pii> vec;
    vector <int> vv;
    for(int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        vec.pb({x, y});
        vv.pb(x);
    }
    sort(vec.begin(), vec.end());
    sort(vv.begin(), vv.end());
    for(int i = 0; i < vec.size(); i++){
        a[i + 1] = vec[i].s;
        b[i + 1] = vec[i].s + vec[i].f;
    }
    t[0].resize(4 * n + 1);
    t[1].resize(4 * n + 1);
    build(1, 1, n);
   // cout << 1;
    while(q--){
        int x, y, z; cin >> x >> y >> z;
        int ind = lower_bound(vv.begin(), vv.end(), x) - vv.begin();
        int ind1 = lower_bound(vv.begin(), vv.end(), z - y) - vv.begin();
        ind++;
        ind1++;
        ind1 = max(ind, ind1);
        //cout << ind << ' ' << ind1 << "\n";
        cout << get(1, 1, n, ind, ind1 - 1, 1, z) + get(1 ,1, n, ind1, n, 0, y) << "\n";
    }
    return 0;
}

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

examination.cpp: In function 'int main()':
examination.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~

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