oj.uz

Submission #330082

# Submission time Handle Problem Language Result Execution time Memory
330082 2020-11-23T19:12:51 Z Falcon Examination (JOI19_examination) C++17
20 / 100
 407 ms 19420 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

struct fenwick_tree {
    int n;
    vector<int> a;
    vector<int> u;

    fenwick_tree(int n_ = 0) : n{n_}, a(n + 1) {}

    void update(int i) {
        for(++i; i <= n; i += i & -i)
            ++a[i], u.push_back(i);
    }

    int pref(int i) const {
        int s{};
        for(++i; i > 0; i -= i & -i)
            s += a[i];
        return s;
    }

    int query(int s, int e) const {
        return pref(e) - pref(s - 1);
    }

    void clear() {
        for(int x : u) a[x] = 0;
        u.clear();
    }
};

struct point {
    int x, y, z, i{-1};
};

namespace std {
    string to_string(const point& p) {
        ostringstream ss;
        ss << "{" << p.x << ", " << p.y << ", " << p.z << ", " << p.i << "}";
        return ss.str();
    }
};

#ifdef DEBUG
#include "debug.hpp"
#endif


int N, Q, M{};
vector<int> ans;
vector<point> points;

fenwick_tree bit;

using it = vector<point>::iterator;
void cdq_dnc(const it s, const it e) {
    if(e - s == 1) return;
    it m = s + (e - s) / 2;
    cdq_dnc(s, m), cdq_dnc(m, e);

    vector<point> tmp; tmp.reserve(e - s);
    for(auto i = s, j = m; i < m || j < e; ) {
        if(i != m && (j == e || i->y >= j->y)) {
            tmp.push_back(*i);
            if(i->i == -1)
                bit.update(i->z);
            ++i;
        } else {
            tmp.push_back(*j);
            if(j->i >= 0) 
                ans[j->i] += bit.query(j->z, M - 1);
            ++j;
        }
    }

    bit.clear();
    for(auto i = tmp.begin(), j = s; j < e; ++i, ++j)
        *j = *i;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef DEBUG
    freopen("debug", "w", stderr);
    #endif

    cin >> N >> Q; points.reserve(N + Q), ans.resize(Q);
    rep(i, N) {
        int S, T; cin >> S >> T;
        points.push_back(point{S, T, S + T, -1});
    }

    rep(i, Q) {
        int X, Y, Z; cin >> X >> Y >> Z;
        points.push_back(point{X, Y, Z, i});
    }

    sort(all(points), [](const point& p, const point& q) {
        return p.x > q.x || (p.x == q.x && p.y > q.y)
            || (p.x == q.x && p.y == q.y && p.z > q.z)
            || (p.x == q.x && p.y == q.y && p.z ==  q.x && p.i < q.i);
    });

    map<int, int> mp;
    for(const auto& p : points) mp[p.z];
    for(auto& p : mp) p.second = M++; 
    for(auto& p : points) p.z = mp[p.z];

    bit = fenwick_tree(M);
    cdq_dnc(all(points));
    
    rep(i, Q) cout << ans[i] << '\n';

    #ifdef DEBUG
    dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC  << "ms" << endl;
    #endif

    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 8 ms 1152 KB Output is correct
8 Correct 8 ms 1132 KB Output is correct
9 Correct 8 ms 1132 KB Output is correct
10 Correct 7 ms 1004 KB Output is correct
11 Correct 7 ms 1004 KB Output is correct
12 Incorrect 5 ms 620 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 16512 KB Output is correct
2 Correct 280 ms 16480 KB Output is correct
3 Correct 269 ms 16480 KB Output is correct
4 Correct 218 ms 15076 KB Output is correct
5 Correct 228 ms 15072 KB Output is correct
6 Correct 114 ms 10996 KB Output is correct
7 Correct 258 ms 17952 KB Output is correct
8 Correct 270 ms 16352 KB Output is correct
9 Correct 257 ms 17692 KB Output is correct
10 Correct 214 ms 13812 KB Output is correct
11 Correct 220 ms 15196 KB Output is correct
12 Correct 91 ms 10484 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 16512 KB Output is correct
2 Correct 280 ms 16480 KB Output is correct
3 Correct 269 ms 16480 KB Output is correct
4 Correct 218 ms 15076 KB Output is correct
5 Correct 228 ms 15072 KB Output is correct
6 Correct 114 ms 10996 KB Output is correct
7 Correct 258 ms 17952 KB Output is correct
8 Correct 270 ms 16352 KB Output is correct
9 Correct 257 ms 17692 KB Output is correct
10 Correct 214 ms 13812 KB Output is correct
11 Correct 220 ms 15196 KB Output is correct
12 Correct 91 ms 10484 KB Output is correct
13 Correct 407 ms 19420 KB Output is correct
14 Correct 373 ms 18784 KB Output is correct
15 Correct 269 ms 16476 KB Output is correct
16 Correct 285 ms 16612 KB Output is correct
17 Incorrect 293 ms 16864 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 8 ms 1152 KB Output is correct
8 Correct 8 ms 1132 KB Output is correct
9 Correct 8 ms 1132 KB Output is correct
10 Correct 7 ms 1004 KB Output is correct
11 Correct 7 ms 1004 KB Output is correct
12 Incorrect 5 ms 620 KB Output isn't correct
13 Halted 0 ms 0 KB -