oj.uz

Submission #839414

# Submission time Handle Problem Language Result Execution time Memory
839414 2023-08-30T02:13:22 Z vjudge1 Examination (JOI19_examination) C++17
0 / 100
 205 ms 13096 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point{
    int x, y, z, idx;
};
namespace BIT{
    const int OFFSET = 10;
    int p = 0;
    vector<pair<int, int>> s;
    void init(int n){
        s.resize(n + OFFSET*2);
    }
    int query(int pos){
        int r = 0;
        for (pos=s.size()-pos-OFFSET; pos; pos -= pos & (-pos))
            r += (s[pos].second == p) * s[pos].first;
        return r;
    }
    void update(int pos, int v){
        for (pos=s.size()-pos-OFFSET; pos < s.size(); pos += pos & (-pos)){
            if (s[pos].second != p) s[pos] = {0, p};
            s[pos].first += v;
        }
    }
    void reset(){
        p++;
    }
}
vector<point> a;
vector<int> result;
void cdq(int start, int end){
    if (start == end) return;
    int mid = (start+end)>>1;
    cdq(start, mid); cdq(mid+1, end);
    vector<pair<point, bool>> s;
    int lptr = start;
    for (int rptr=mid+1; rptr<=end; rptr++){
        while (lptr <= mid && a[lptr].y >= a[rptr].y)
            s.emplace_back(a[lptr++], 0);
        s.emplace_back(a[rptr], 1);
    }
    while (lptr <= mid) s.emplace_back(a[lptr++], 0);
    BIT::reset();
    for (const pair<point, bool> &c: s){
        if (c.second && c.first.idx != -1)
            result[c.first.idx] += BIT::query(c.first.x);
        if (!c.second && c.first.idx == -1)
            BIT::update(c.first.x, 1);
    }
    for (int i=0; i<s.size(); i++)
        a[start+i] = s[i].first;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    for (int i=0; i<n; i++){
        int s, t; cin >> s >> t;
        a.push_back({s, t, s+t, -1});
    }
    for (int i=0; i<q; i++){
        int x, y, z; cin >> x >> y >> z;
        a.push_back({x, y, z, i});
    }
    sort(a.begin(), a.end(), [](const point &a, const point &b){
        return a.x < b.x;
    });
    for (int lptr=0, rptr=0; lptr<a.size(); lptr=rptr){
        int value = a[lptr].x;
        while (rptr<a.size() && value == a[rptr].x)
            a[rptr++].x = lptr;
    }
    BIT::init(n+q);
    sort(a.begin(), a.end(), [](const point &a, const point &b){
        return a.z > b.z;
    });
    result.resize(q);
    cdq(0, a.size()-1);
    for (int v: result) cout << v << "\n";
}

Compilation message

examination.cpp: In function 'void BIT::update(int, int)':
examination.cpp:22:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (pos=s.size()-pos-OFFSET; pos < s.size(); pos += pos & (-pos)){
      |                                       ~~~~^~~~~~~~~~
examination.cpp: In function 'void cdq(int, int)':
examination.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<point, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i=0; i<s.size(); i++)
      |                   ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:69:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int lptr=0, rptr=0; lptr<a.size(); lptr=rptr){
      |                              ~~~~^~~~~~~~~
examination.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (rptr<a.size() && value == a[rptr].x)
      |                ~~~~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 4 ms 704 KB Output is correct
11 Correct 4 ms 776 KB Output is correct
12 Incorrect 5 ms 724 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 12992 KB Output is correct
2 Correct 174 ms 13056 KB Output is correct
3 Correct 190 ms 13032 KB Output is correct
4 Correct 150 ms 13060 KB Output is correct
5 Correct 135 ms 12988 KB Output is correct
6 Incorrect 116 ms 13096 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 12992 KB Output is correct
2 Correct 174 ms 13056 KB Output is correct
3 Correct 190 ms 13032 KB Output is correct
4 Correct 150 ms 13060 KB Output is correct
5 Correct 135 ms 12988 KB Output is correct
6 Incorrect 116 ms 13096 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 4 ms 704 KB Output is correct
11 Correct 4 ms 776 KB Output is correct
12 Incorrect 5 ms 724 KB Output isn't correct
13 Halted 0 ms 0 KB -