oj.uz

답안 #208188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208188 2020-03-10T08:27:06 Z paradox Examination (JOI19_examination) C++17
20 / 100
 433 ms 37088 KB 
#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 = 2e5;
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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 19804 KB Output is correct
2 Correct 363 ms 19808 KB Output is correct
3 Correct 376 ms 19808 KB Output is correct
4 Correct 219 ms 14940 KB Output is correct
5 Correct 229 ms 14996 KB Output is correct
6 Correct 126 ms 8924 KB Output is correct
7 Correct 357 ms 18796 KB Output is correct
8 Correct 362 ms 18828 KB Output is correct
9 Correct 326 ms 17736 KB Output is correct
10 Correct 235 ms 14760 KB Output is correct
11 Correct 237 ms 14852 KB Output is correct
12 Correct 109 ms 8932 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 19804 KB Output is correct
2 Correct 363 ms 19808 KB Output is correct
3 Correct 376 ms 19808 KB Output is correct
4 Correct 219 ms 14940 KB Output is correct
5 Correct 229 ms 14996 KB Output is correct
6 Correct 126 ms 8924 KB Output is correct
7 Correct 357 ms 18796 KB Output is correct
8 Correct 362 ms 18828 KB Output is correct
9 Correct 326 ms 17736 KB Output is correct
10 Correct 235 ms 14760 KB Output is correct
11 Correct 237 ms 14852 KB Output is correct
12 Correct 109 ms 8932 KB Output is correct
13 Runtime error 433 ms 37088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -