oj.uz

Submission #720646

# Submission time Handle Problem Language Result Execution time Memory
720646 2023-04-08T18:35:03 Z ssense Examination (JOI19_examination) C++14
100 / 100
 229 ms 21096 KB 
#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu

bool cmp(array<int, 4> a, array<int, 4> b)
{
    if(a[2] != b[2])
    {
        return a[2] > b[2];
    }
    return a[3] < b[3];
}


struct BIT
{
    int n;
    vector<int> bit;
    
    BIT(int n_now)
    {
        n = n_now;
        bit.assign(n+1, 0);
    }
    
    void add(int idx, int delta)
    {
        for(int i = idx; i <= n; i = i|(i+1))
        {
            bit[i]+=delta;
        }
    }
    
    int get(int l)
    {
        int sum = 0;
        for(int i = l; i >= 0; i = (i&(i+1))-1)
        {
            sum+=bit[i];
        }
        return sum;
    }
    
    int get(int l, int r)
    {
        return get(r)-get(l-1);
    }
};

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<array<int, 4>> queries;
    vector<int> ans(q);
    vector<int> vals;
    for(int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        vals.pb(a);
        vals.pb(b);
        queries.pb({a, b, a+b, -1});
    }
    for(int i = 0; i < q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        vals.pb(a);
        vals.pb(b);
        queries.pb({a, b, max(a+b, c), i});
    }
    sort(all(vals));
     
    auto idx = [&](int a) {
        return lower_bound(vals.begin(), vals.end(), a) - vals.begin() + 1;
    };
    int total = 0;
    sort(all(queries), cmp);
    BIT a(500005), b(500005);
    for(auto x : queries)
    {
        if(x[3] == -1)
        {
            a.add(idx(x[0]), 1);
            b.add(idx(x[1]), 1);
            total++;
        }
        else
        {
            ans[x[3]] = a.get(idx(x[0]), 500005)+b.get(idx(x[1]), 500005)-total;
        }
    }
    for(int i = 0; i < q; i++)
    {
        cout << ans[i] << endl;
    }
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}


/*
 
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
 */

Compilation message

examination.cpp: In member function 'void prefix_sum::build(std::vector<long long int>)':
examination.cpp:20:667: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8124 KB Output is correct
6 Correct 5 ms 8128 KB Output is correct
7 Correct 11 ms 8656 KB Output is correct
8 Correct 10 ms 8744 KB Output is correct
9 Correct 10 ms 8704 KB Output is correct
10 Correct 9 ms 8672 KB Output is correct
11 Correct 10 ms 8656 KB Output is correct
12 Correct 8 ms 8524 KB Output is correct
13 Correct 11 ms 8668 KB Output is correct
14 Correct 10 ms 8656 KB Output is correct
15 Correct 10 ms 8672 KB Output is correct
16 Correct 8 ms 8648 KB Output is correct
17 Correct 9 ms 8648 KB Output is correct
18 Correct 6 ms 8584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 20548 KB Output is correct
2 Correct 217 ms 21028 KB Output is correct
3 Correct 196 ms 21084 KB Output is correct
4 Correct 137 ms 20536 KB Output is correct
5 Correct 147 ms 20608 KB Output is correct
6 Correct 129 ms 19804 KB Output is correct
7 Correct 229 ms 21092 KB Output is correct
8 Correct 191 ms 21072 KB Output is correct
9 Correct 182 ms 21096 KB Output is correct
10 Correct 121 ms 20396 KB Output is correct
11 Correct 124 ms 20356 KB Output is correct
12 Correct 91 ms 19504 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 20548 KB Output is correct
2 Correct 217 ms 21028 KB Output is correct
3 Correct 196 ms 21084 KB Output is correct
4 Correct 137 ms 20536 KB Output is correct
5 Correct 147 ms 20608 KB Output is correct
6 Correct 129 ms 19804 KB Output is correct
7 Correct 229 ms 21092 KB Output is correct
8 Correct 191 ms 21072 KB Output is correct
9 Correct 182 ms 21096 KB Output is correct
10 Correct 121 ms 20396 KB Output is correct
11 Correct 124 ms 20356 KB Output is correct
12 Correct 91 ms 19504 KB Output is correct
13 Correct 219 ms 21096 KB Output is correct
14 Correct 213 ms 21016 KB Output is correct
15 Correct 189 ms 21020 KB Output is correct
16 Correct 143 ms 20980 KB Output is correct
17 Correct 144 ms 20924 KB Output is correct
18 Correct 103 ms 19880 KB Output is correct
19 Correct 226 ms 20960 KB Output is correct
20 Correct 208 ms 20968 KB Output is correct
21 Correct 206 ms 20884 KB Output is correct
22 Correct 128 ms 20448 KB Output is correct
23 Correct 134 ms 20456 KB Output is correct
24 Correct 95 ms 19444 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8124 KB Output is correct
6 Correct 5 ms 8128 KB Output is correct
7 Correct 11 ms 8656 KB Output is correct
8 Correct 10 ms 8744 KB Output is correct
9 Correct 10 ms 8704 KB Output is correct
10 Correct 9 ms 8672 KB Output is correct
11 Correct 10 ms 8656 KB Output is correct
12 Correct 8 ms 8524 KB Output is correct
13 Correct 11 ms 8668 KB Output is correct
14 Correct 10 ms 8656 KB Output is correct
15 Correct 10 ms 8672 KB Output is correct
16 Correct 8 ms 8648 KB Output is correct
17 Correct 9 ms 8648 KB Output is correct
18 Correct 6 ms 8584 KB Output is correct
19 Correct 201 ms 20548 KB Output is correct
20 Correct 217 ms 21028 KB Output is correct
21 Correct 196 ms 21084 KB Output is correct
22 Correct 137 ms 20536 KB Output is correct
23 Correct 147 ms 20608 KB Output is correct
24 Correct 129 ms 19804 KB Output is correct
25 Correct 229 ms 21092 KB Output is correct
26 Correct 191 ms 21072 KB Output is correct
27 Correct 182 ms 21096 KB Output is correct
28 Correct 121 ms 20396 KB Output is correct
29 Correct 124 ms 20356 KB Output is correct
30 Correct 91 ms 19504 KB Output is correct
31 Correct 219 ms 21096 KB Output is correct
32 Correct 213 ms 21016 KB Output is correct
33 Correct 189 ms 21020 KB Output is correct
34 Correct 143 ms 20980 KB Output is correct
35 Correct 144 ms 20924 KB Output is correct
36 Correct 103 ms 19880 KB Output is correct
37 Correct 226 ms 20960 KB Output is correct
38 Correct 208 ms 20968 KB Output is correct
39 Correct 206 ms 20884 KB Output is correct
40 Correct 128 ms 20448 KB Output is correct
41 Correct 134 ms 20456 KB Output is correct
42 Correct 95 ms 19444 KB Output is correct
43 Correct 205 ms 20924 KB Output is correct
44 Correct 204 ms 20836 KB Output is correct
45 Correct 199 ms 20904 KB Output is correct
46 Correct 151 ms 20964 KB Output is correct
47 Correct 149 ms 20820 KB Output is correct
48 Correct 107 ms 19788 KB Output is correct
49 Correct 200 ms 20896 KB Output is correct
50 Correct 205 ms 20892 KB Output is correct
51 Correct 209 ms 20892 KB Output is correct
52 Correct 144 ms 20708 KB Output is correct
53 Correct 127 ms 20696 KB Output is correct