oj.uz

Submission #1022189

# Submission time Handle Problem Language Result Execution time Memory
1022189 2024-07-13T10:52:06 Z dosts Examination (JOI19_examination) C++17
2 / 100
 517 ms 1048576 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 3e5+1,inf = 2e9;

struct Query {
    int id,x,y,z;
};


vi v;


int idx(int x) {
    return upper_bound(all(v),x) - v.begin();
}

struct BIT {
    int n,m;
    vector<vi> bit;

    BIT(int nn,int mm) {
        n = nn,
        m = mm;
        bit.assign(n+1,vi(m+1,0));
    }

    void put(int x,int y,int v) {
        for (int i=x;i<=n;i+=i&-i) {
            for (int j=y;j<=n;j+=j&-j) {
                bit[i][j]+=v;
            }
        }
    } 
    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+=bit[i][j];
            }
        }
        return ans;
    }
};

void solve() { 
    int n,q;
    cin >> n >> q;
    vi a(n+1),b(n+1);
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i];
    vi inds(n+1);
    iota(inds.begin(),inds.end(),0);
    sort(inds.begin()+1,inds.end(),[&](int x,int y) {
        return a[x]+b[x] < a[y]+b[y];
    });
    vector<Query> queries(q);
    vi ans(q);
    for (int i=0;i<q;i++) {
        cin >> queries[i].x >> queries[i].y >> queries[i].z;
        queries[i].id = i;
    }
    for (int i=1;i<=n;i++) v.push_back(-a[i]),v.push_back(-b[i]);
    for (int i=1;i<=q;i++) v.push_back(-queries[i].x),v.push_back(-queries[i].y);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    sort(queries.begin(), queries.end(),[&](const Query& x,const Query& y) {
        return x.z > y.z;
    });
    int sz = v.size();
    BIT ft(sz,sz);
    int ptr = n+1;
    for (auto Q : queries) {
        int X = Q.x, Y = Q.y, Z = Q.z,ID = Q.id;
        while (ptr > 1 && a[inds[ptr-1]]+b[inds[ptr-1]] >= Z) {
            --ptr;
            ft.put(idx(-a[inds[ptr]]),idx(-b[inds[ptr]]),1);
        }
        ans[Q.id] = ft.get(idx(-X),idx(-Y));
    }
    for (int i=0;i<q;i++) cout << ans[i] << '\n';
}      
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message

examination.cpp: In function 'void solve()':
examination.cpp:81:39: warning: unused variable 'ID' [-Wunused-variable]
   81 |         int X = Q.x, Y = Q.y, Z = Q.z,ID = Q.id;
      |                                       ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 241 ms 564916 KB Output is correct
8 Correct 334 ms 564712 KB Output is correct
9 Correct 238 ms 564816 KB Output is correct
10 Correct 70 ms 142328 KB Output is correct
11 Correct 64 ms 142420 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 267 ms 564820 KB Output is correct
14 Correct 263 ms 564744 KB Output is correct
15 Correct 261 ms 564880 KB Output is correct
16 Correct 72 ms 141852 KB Output is correct
17 Correct 81 ms 141940 KB Output is correct
18 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 517 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 517 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 241 ms 564916 KB Output is correct
8 Correct 334 ms 564712 KB Output is correct
9 Correct 238 ms 564816 KB Output is correct
10 Correct 70 ms 142328 KB Output is correct
11 Correct 64 ms 142420 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 267 ms 564820 KB Output is correct
14 Correct 263 ms 564744 KB Output is correct
15 Correct 261 ms 564880 KB Output is correct
16 Correct 72 ms 141852 KB Output is correct
17 Correct 81 ms 141940 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Runtime error 517 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -