제출 #1342616

#제출 시각아이디문제언어결과실행 시간메모리
1342616SemicolonExamination (JOI19_examination)C++20
100 / 100
810 ms77360 KiB
/**
 *     Author: Lưu Diệp Thành (Save Diệp Thành)
 *     Le Hong Phong High School for the Gifted (i2528)
**/
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define ushort unsigned short
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORN(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define endl '\n'
#define sz(x) (int)x.size()
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define ins insert
#define segleft (id<<1)
#define segright (id<<1|1)
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
const int MOD = 1e9+7;

struct Fenwick {
    vector<vector<int>> pos;
    vector<vector<int>> bit;
    int n;

    Fenwick() {}

    void init(int _n) {
        n = _n;
        pos.assign(n+1, {});
        bit.assign(n+1, {});
    }

    void fakeadd(int u, int v) {
        int idx = u;
        while(idx <= n) {
            pos[idx].pb(v);
            idx += (idx & -idx);
        }
    }

    void fakeget(int u, int v) {
        int idx = u;
        while(idx > 0) {
            pos[idx].pb(v);
            idx -= (idx & -idx);
        }
    }

    void compress() {
        FOR(i, 1, n) {
            sort(all(pos[i]));
            pos[i].erase(unique(all(pos[i])), pos[i].end());
            bit[i].assign(sz(pos[i])+5, 0);
        }
    }

    int getindex(int i, int j) {
        return lower_bound(all(pos[i]), j) - pos[i].begin() + 1;
    }

    void add(int x, int y, int v) {
        for(int i = x; i <= n; i += (i & -i)) {
            for(int j = getindex(i, y); j < sz(bit[i]); j += (j & -j)) {
                bit[i][j] += v;
            }
        }
    }

    int get(int x, int y) {
        int sum = 0;
        for(int i = x; i > 0; i -= (i & -i)) {
            for(int j = getindex(i, y); j > 0; j -= (j & -j)) {
                sum += bit[i][j];
            }
        }
        return sum;
    }

    int query(int x1, int y1, int x2, int y2) {
        return get(x2, y2) - get(x1-1, y2) - get(x2, y1-1) + get(x1-1, y1-1);
    }
};

struct infoValue {
    int s,t,sum;
};

struct infoQuery {
    int x,y,z;
    int idQuery;
};

const int N = 1e5+5;
Fenwick bit;
vector<infoValue> a(N);
vector<infoQuery> query(N);
vector<int> ans(N);
vector<int> value;
int n,q;

void compress() {
    sort(all(value));
    value.erase(unique(all(value)), value.end());
}

int getvalue(int x) {
    return lower_bound(all(value), x) - value.begin() + 1;
}

void precalc() {
    int j = 1;
    FOR(i, 1, q) {
        while(j <= n && a[j].sum >= query[i].z) {
            bit.fakeadd(a[j].s, a[j].t);
            j++;
        }
        int x1 = query[i].x, y1 = query[i].y, x2 = sz(value), y2 = sz(value);
        bit.fakeget(x2, y2);
        bit.fakeget(x1-1, y2);
        bit.fakeget(x2, y1-1);
        bit.fakeget(x1-1, y1-1);
    }
}

void calc() {
    int j = 1;
    FOR(i, 1, q) {
        while(j <= n && a[j].sum >= query[i].z) {
            bit.add(a[j].s, a[j].t, 1);
            j++;
        }
        int x1 = query[i].x, y1 = query[i].y, x2 = sz(value), y2 = sz(value);
        ans[query[i].idQuery] = bit.query(x1, y1, x2, y2);
    }
}

void Semicolon() {
    cin >> n >> q;

    FOR(i, 1, n) {
        cin >> a[i].s >> a[i].t;
        a[i].sum = a[i].s + a[i].t;
        value.pb(a[i].s);
        value.pb(a[i].t);
    }

    FOR(i, 1, q) {
        cin >> query[i].x >> query[i].y >> query[i].z;
        query[i].idQuery = i;
        value.pb(query[i].x);
        value.pb(query[i].y);
    }

    compress();
    bit.init(sz(value)+5);

    FOR(i, 1, n) {
        a[i].s = getvalue(a[i].s);
        a[i].t = getvalue(a[i].t);
    }

    FOR(i, 1, q) {
        query[i].x = getvalue(query[i].x);
        query[i].y = getvalue(query[i].y);
    }

    sort(a.begin()+1, a.begin()+n+1, [](infoValue &left, infoValue &right) {
        return left.sum > right.sum;
    });

    sort(query.begin()+1, query.begin()+q+1, [](infoQuery &left, infoQuery &right) {
        return left.z > right.z;
    });

    precalc();
    bit.compress();
    calc();

    FOR(i, 1, q) {
        cout << ans[i] << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
    int t = 1;
    //cin >> t;
    while(t--) Semicolon();

    cerr << endl;
    cerr << "Time elapsed: " << TIME << " s.\n ";
    return (0 ^ 0);
}

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

examination.cpp: In function 'int main()':
examination.cpp:194:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |     if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
      |                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...