Submission #208190

#	Time	Username	Problem	Language	Result	Execution time	Memory
208190		paradox	Examination (JOI19_examination)	C++17	20 / 100	401 ms	43748 KiB

examination

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define vi vector<int>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
typedef long long ll;
typedef short inth;
 
const int N = 8e5;
const int M = N + 7;
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 17;

map<int, int> px, py;

struct Point {
    int x, y;
    int power;
    int id;

    int comx, comy;

    Point(int x, int y, int id, int new_power = -1) : 
            x(x), y(y), power(new_power), id(id), comx(0), comy(0) {
        if (new_power == -1)
            power = x + y;
    };

    void compress() {
        comx = px[x];
        comy = py[y];
    }
};

vector<Point> p, w[2];

int n, m;

inline void read() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        int cx, cy;
        scanf("%d %d", &cx, &cy);

        p.pb(Point(cx, cy, i));
    }

    for (int i = 1; i <= m; ++i) {
        int cx, cy, cs;
        scanf("%d %d %d", &cx, &cy, &cs);

        if (cx + cy >= cs)
            w[0].pb(Point(cx, cy, i, cs));
        else
            w[1].pb(Point(cx, cy, i, cs));
    }
}

inline void compress() {
    vector<int> ordx, ordy;

    for (int i = 0; i < n; ++i) {
        ordx.pb(p[i].x);
        ordy.pb(p[i].y);
    }

    for (int j = 0; j < 2; ++j)
        for (int i = 0; i < sz(w[j]); ++i) {
            ordx.pb(w[j][i].x);
            ordy.pb(w[j][i].y);
        }

    sort(all(ordx));
    sort(all(ordy));

    int timx = 0, timy = 0;
    for (int i = 0; i < sz(ordx); ++i) {
        if (!i || ordx[i] != ordx[i - 1])
            px[ordx[i]] = ++timx;
        if (!i || ordy[i] != ordy[i - 1])
            py[ordy[i]] = ++timy;
    }

    for (int i = 0; i < n; ++i)
        p[i].compress();
    for (int i = 0; i < sz(w[0]); ++i)
        w[0][i].compress();
    for (int i = 0; i < sz(w[1]); ++i)
        w[1][i].compress();
}

struct Tree {
    int g[M];

    void build() {
        for (int i = 0; i < M; ++i)
            g[i] = 0;
    }

    void upd(int pos, int val, int v = 1, int tl = 1, int tr = N) {
        if (tl == tr) {
            g[v] += val;
            return;
        }

        int tm = (tl + tr) >> 1;

        if (pos <= tm)
            upd(pos, val, v << 1, tl, tm);
        else
            upd(pos, val, v << 1 | 1, tm + 1, tr);

        g[v] = g[v << 1] + g[v << 1 | 1];
    }

    int get(int l, int r, int v = 1, int tl = 1, int tr = N) {
        if (tr < l || r < tl)
            return 0;
        
        if (l <= tl && tr <= r)
            return g[v];
        
        int tm = (tl + tr) >> 1;
        
        int f = get(l, r, v << 1, tl, tm);
        int s = get(l, r, v << 1 | 1, tm + 1, tr);

        return f + s;
    }

} tree[2];

inline bool cmpX(const Point& a, const Point& b) {
    return a.x > b.x;
}

int ans[M];

inline void solve1() {
    sort(w[0].begin(), w[0].end(), cmpX);
    sort(all(p), cmpX);

    int j = 0;
    tree[0].build();

    for (int i = 0; i < sz(w[0]); ++i) {
        while (j < sz(p) && p[j].x >= w[0][i].x) {
            tree[0].upd(p[j].comy, 1);
            ++j;
        }

        int res = tree[0].get(w[0][i].comy, N);

        ans[w[0][i].id] = res;
    }
}

inline bool cmpPower(const Point& a, const Point& b) {
    return a.power > b.power;
}

inline void solve2() {
    sort(w[1].begin(), w[1].end(), cmpPower);
    sort(all(p), cmpPower);

    int j = 0;
    tree[0].build();
    tree[1].build();

    for (int i = 0; i < sz(w[1]); ++i) {
        while (j < sz(p) && p[j].power >= w[1][i].power) {

            tree[0].upd(p[j].comx, 1);
            tree[1].upd(p[j].comy, 1);

            ++j;
        }

        int res = tree[0].get(1, w[1][i].comx - 1) + tree[1].get(1, w[1][i].comy - 1);

        ans[w[1][i].id] = j - res;

    }
}

inline void out() {
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
}

int main() {

    read();

    compress();
    
    solve1();
    solve2();

    out();

    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void read()':
examination.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &cx, &cy);
         ~~~~~^~~~~~~~~~~~~~~~~~~
examination.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &cx, &cy, &cs);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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