제출 #1350400

#제출 시각아이디문제언어결과실행 시간메모리
1350400dex111222333444555Examination (JOI19_examination)C++20
100 / 100
140 ms10112 KiB
#include <bits/stdc++.h>

#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define lli pair<long long, int>
#define dbg(x) "[" #x " = " << x << "]"

using namespace std;

const int MAXN = 1e5 + 5;

struct fenwickTree{
    int n;
    vector<int > bit;

    fenwickTree(int _n = 0): n(_n){
        bit.assign(n + 1, 0);
    }

    void update(int pos, const int &delta){
        for(; pos > 0; pos ^= pos & -pos) bit[pos] += delta;
    }

    int get(int pos){
        int sum = 0;
        for(; pos <= n; pos += pos & -pos) sum += bit[pos];
        return sum;
    }
};

struct P{
    int x, y, z, id;
    bool type;

    P(int _x = 0, int _y = 0, int _z = 0, int _id = 0, bool _type = 0):
        x(_x), y(_y), z(_z), id(_id), type(_type) {};

    bool operator <(const P &other) const{
        if (x != other.x) return x > other.x;
        return type < other.type;
    }
};

int numVal, numQuery, res[MAXN];
P val[MAXN << 1], tmp[MAXN << 1];
vector<int > comp;
fenwickTree bit;

void input(){
    cin >> numVal >> numQuery;

    for(int i = 1; i <= numVal; i++){
        cin >> val[i].x >> val[i].y;
        val[i].z = (val[i].x + val[i].y);
        val[i].type = 0;
        comp.push_back(val[i].z);
    }

    for(int i = numVal + 1; i <= numVal + numQuery; i++){
        cin >> val[i].x >> val[i].y >> val[i].z;
        val[i].id = i - numVal; val[i].type = 1;
    }
}

void dnc(const int &L, const int &R){
    if (L == R) return;

    int M = (L + R) >> 1;

    dnc(L, M);
    dnc(M + 1, R);

//    cout << "DNC " << L << ' ' << R << '\n';

    int i = L, j = M + 1, pos = L;

    vector<int > rollback;

    while(i <= M && j <= R){
        if (val[i].y >= val[j].y){
            if (!val[i].type){
                bit.update(val[i].z, +1);
                rollback.push_back(val[i].z);
            }
            tmp[pos++] = val[i++];

        }else{
            if (val[j].type) res[val[j].id] += bit.get(val[j].z);
            tmp[pos++] = val[j++];

        }
    }

    while(i <= M){
        if (!val[i].type){
            bit.update(val[i].z, +1);
            rollback.push_back(val[i].z);
        }
        tmp[pos++] = val[i++];

    }

    while(j <= R){
        if (val[j].type) res[val[j].id] += bit.get(val[j].z);
        tmp[pos++] = val[j++];

    }

    for(int i = L; i <= R; i++) val[i] = tmp[i];
    for(int x: rollback) bit.update(x, -1);
}

int getPos(const int &pos){
    return lower_bound(all(comp), pos) - begin(comp) + 1;
}

void solve(){
    sort(all(comp));
    comp.resize(unique(all(comp)) - begin(comp));

    sort(val + 1, val + 1 + numVal + numQuery);

    for(int i = 1; i <= numVal + numQuery; i++){
        val[i].z = getPos(val[i].z);
    }

    bit = fenwickTree(siz(comp));

    dnc(1, numVal + numQuery);

    for(int q = 1; q <= numQuery; q++){
        cout << res[q] << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    solve();
    cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}

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

examination.cpp: In function 'int main()':
examination.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...