oj.uz

Submission #1116498

# Submission time Handle Problem Language Result Execution time Memory
1116498 2024-11-21T17:50:53 Z gdragon Examination (JOI19_examination) C++17
20 / 100
 1724 ms 190812 KB 
#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 1e5 + 100;
const int INF = 2e9 + 7;
const int mod = 1e9 + 7;
map<int, int> m[N];
void update(int x, int y, int c) {
    for(int i = x; i < N; i += i & -i) {
        for(int j = y; j < N; j += j & -j) m[i][j] += c;
    }
}
int get(int x, int y) {
    int ans = 0;
    for(int i = x; i > 0; i -= i & -i) {
        for(int j = y; j > 0; j -= j & -j) ans += m[i][j];
    }
    return ans;
}
struct Fenwick {
    int n;
    vector<int> v;
    Fenwick(int _n = 0) {
        n = _n;
        v.assign(n + 5, 0);
    }
    void update(int x, int c) {
        for(; x > 0; x -= x & -x) v[x] += c;
    }
    int get(int x) {
        int ans = 0;
        for(; x <= n; x += x & -x) ans += v[x];
        return ans;
    }
} fw1, fw2;
struct Fenwick1 {
    int n;
    vector<int> v;
    Fenwick1(int _n = 0) {
        n = _n;
        v.assign(n + 5, 0);
    }
    void update(int x, int c) {
        for(; x <= n; x += x & -x) v[x] += c;
    }
    int get(int x) {
        int ans = 0;
        for(; x > 0; x -= x & -x) ans += v[x];
        return ans;
    }
} fw;
struct Point {
    int x, y;
    int id, pos;
    Point(int _x = 0, int _y = 0, int _id = 0, int _pos = 0) {
        x = _x; y = _y; id = _id; pos = _pos;
    }
    bool operator < (const Point &other) {
        return pos < other.pos;
    }
};
struct CompareTask {
    bool operator()(const Point& a, const Point& b) {
        return a.pos > b.pos; // Lower number has higher priority
    }
};
int n, q;
int ans[N];
pair<int, int> a[N];
vector<pair<int, pair<int, int>>> queries[N];
void read() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
}
vector<int> valB, valC;
void compress() {
    for(int i = 1; i <= n; i++) {
        valB.push_back(a[i].se);
        valC.push_back(a[i].fi + a[i].se);
    }
    valB.push_back(INF);
    valC.push_back(INF);
    sort(ALL(valB));
    valB.erase(unique(ALL(valB)), valB.end());
    sort(ALL(valC));
    valC.erase(unique(ALL(valC)), valC.end());
}
void solve() {
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= q; i++) {
        int A, B, C; cin >> A >> B >> C;
        int p = lower_bound(a + 1, a + n + 1, mp(A, 0)) - a;
        if (p > n) ans[i] = 0;
        else {
            queries[p].push_back({i, mp(B, C)});
        }
    }
    compress();
    fw1 = Fenwick(SZ(valB));
    fw2 = Fenwick(SZ(valC));
    vector<Point> pointUpdate, pointGet;
    int timer = 0;
    for(int i = n; i >= 1; i--) {
        int b = lower_bound(ALL(valB), a[i].se) - valB.begin() + 1;
        fw1.update(b, 1);
        int c = lower_bound(ALL(valC), a[i].fi + a[i].se) - valC.begin() + 1;
        fw2.update(c, 1);
        update(b, c, 1);
        pointUpdate.push_back(Point(b, c, 0, ++timer));
        // cerr << "BC: " << b << ' ' << c << endl;
        for(auto &query: queries[i]) {
            int id = query.fi;
            int B = query.se.fi;
            int C = query.se.se;
            B = lower_bound(ALL(valB), B) - valB.begin() + 1;
            C = lower_bound(ALL(valC), C) - valC.begin() + 1;
            pointGet.push_back(Point(B - 1, C - 1, id, ++timer));
            // cerr << id << ' ' << i << ' ' << n - i + 1 << endl;
            ans[id] = fw1.get(B) + fw2.get(C) - (n - i + 1);
            // ans[id] += get(B - 1, C - 1);
            // for(int j = i; j <= n; j++) if (a[j].se < query.se.fi && a[j].fi + a[j].se < query.se.se) {
            //     ++ans[id];
            // }
        }
    }
    sort(ALL(pointUpdate), [&](const Point &p1, const Point &p2) {
        return (p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y));
    });
    fw = Fenwick1(SZ(valC));
    priority_queue<Point, vector<Point>, CompareTask> heap;
    int j = 0;
    for(auto &p: pointGet) {
        while(j < SZ(pointUpdate)) {
            if (pointUpdate[j].x > p.x || (pointUpdate[j].x == p.x && pointUpdate[j].y > p.y)) break;
            if (pointUpdate[j].pos > p.pos) {
                heap.push(pointUpdate[j]);
            }
            else fw.update(pointUpdate[j].y, 1);
            ++j;
        } 
        while(!heap.empty()) {
            Point tmp = heap.top(); 
            if (tmp.pos > p.pos) break;
            assert(tmp.pos < p.pos);
            heap.pop();
            fw.update(tmp.y, 1);
        }
        ans[p.id] += fw.get(p.y);
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1724 ms 190812 KB Output is correct
2 Correct 1513 ms 190300 KB Output is correct
3 Correct 1677 ms 189972 KB Output is correct
4 Correct 991 ms 75808 KB Output is correct
5 Correct 697 ms 76456 KB Output is correct
6 Correct 290 ms 19232 KB Output is correct
7 Correct 1632 ms 186552 KB Output is correct
8 Correct 1660 ms 187012 KB Output is correct
9 Correct 1633 ms 184932 KB Output is correct
10 Correct 454 ms 65724 KB Output is correct
11 Correct 1201 ms 67928 KB Output is correct
12 Correct 300 ms 13508 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1724 ms 190812 KB Output is correct
2 Correct 1513 ms 190300 KB Output is correct
3 Correct 1677 ms 189972 KB Output is correct
4 Correct 991 ms 75808 KB Output is correct
5 Correct 697 ms 76456 KB Output is correct
6 Correct 290 ms 19232 KB Output is correct
7 Correct 1632 ms 186552 KB Output is correct
8 Correct 1660 ms 187012 KB Output is correct
9 Correct 1633 ms 184932 KB Output is correct
10 Correct 454 ms 65724 KB Output is correct
11 Correct 1201 ms 67928 KB Output is correct
12 Correct 300 ms 13508 KB Output is correct
13 Incorrect 1566 ms 190308 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8528 KB Output isn't correct
2 Halted 0 ms 0 KB -