oj.uz

Submission #1079855

# Submission time Handle Problem Language Result Execution time Memory
1079855 2024-08-29T02:32:40 Z KhoaDuy Examination (JOI19_examination) C++14
0 / 100
 397 ms 27820 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
struct cube{
    int a,b,c,idx;
};
const int MAXN=1e5;
int ans[MAXN]={0};
int bit[2*MAXN+1]={0};
void update(int i,int x){
    for(;i<=2*MAXN;i+=(i&(-i))){
        bit[i]+=x;
    }
}
int pre(int i){
    int curr=0;
    for(;i;i-=(i&(-i))){
        curr+=bit[i];
    }
    return curr;
}
int query(int l,int r){
    return pre(r)-pre(l-1);
}
bool cmp(cube &a,cube &b){
    return (a.b>b.b);
}
bool cmp2(cube &a,cube &b){
    return (a.a<b.a);
}
void dnc(vector<cube> &v){
    if(v.size()<=1){
        return;
    }
    int mid=(v.size()>>1);
    vector<cube> v1,v2;
    for(int i=0;i<mid;i++){
        v1.push_back(v[i]);
    }
    for(int i=mid;i<v.size();i++){
        v2.push_back(v[i]);
    }
    dnc(v1),dnc(v2);
    sort(v.begin(),v.end(),cmp);
    /*cout << "GOT" << endl;
    cout << "V1: " << endl;
    for(int i=0;i<v1.size();i++){
        cout << v1[i].a << ' ' << v1[i].b << ' ' << v1[i].c << ' ' << v1[i].idx << endl;
    }
    cout << "V2: " << endl;
    for(int i=0;i<v2.size();i++){
        cout << v2[i].a << ' ' << v2[i].b << ' ' << v2[i].c << ' ' << v2[i].idx << endl;
    }*/
    int ptr=0;
    for(int i=0;i<v2.size();i++){
        while(ptr<v1.size()&&v1[ptr].b>v2[i].b){
            if(v1[ptr].idx!=-1){
                ans[v1[ptr].idx]+=query(v1[ptr].c,2*MAXN);
            }
            ptr++;
        }
        if(v2[i].idx==-1){
            update(v2[i].c,1);
        }
    }
    while(ptr<v1.size()){
        if(v1[ptr].idx!=-1){
            ans[v1[ptr].idx]+=query(v1[ptr].c,2*MAXN);
        }
        ptr++;
    }
    for(int i=0;i<v2.size();i++){
        if(v2[i].idx==-1){
            update(v2[i].c,-1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    vector<cube> v;
    map<int,int> mp;
    for(int i=0;i<n;i++){
        int s,t;
        cin >> s >> t;
        v.push_back({s,t,s+t,-1});
        mp[s+t]=1;
    }
    for(int i=0;i<q;i++){
        int x,y,z;
        cin >> x >> y >> z;
        v.push_back({x,y,z,i});
        mp[z]=1;
    }
    int idx=1;
    for(pair<const int,int> &x:mp){
        x.second=idx;
        idx++;
    }
    for(int i=0;i<v.size();i++){
        v[i].c=mp[v[i].c];
    }
    for(int i=0;i<v.size();i++){
    //    cout << v[i].a << ' ' << v[i].b << ' ' << v[i].c << ' ' << v[i].idx << endl;
    }
    sort(v.begin(),v.end(),cmp2);
    dnc(v);
    for(int i=0;i<q;i++){
        cout << ans[i] << endl;
    }
}

Compilation message

examination.cpp: In function 'void dnc(std::vector<cube>&)':
examination.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=mid;i<v.size();i++){
      |                   ~^~~~~~~~~
examination.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<v2.size();i++){
      |                 ~^~~~~~~~~~
examination.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(ptr<v1.size()&&v1[ptr].b>v2[i].b){
      |               ~~~^~~~~~~~~~
examination.cpp:67:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(ptr<v1.size()){
      |           ~~~^~~~~~~~~~
examination.cpp:73:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<v2.size();i++){
      |                 ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:103:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:106:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 10 ms 1496 KB Output is correct
8 Correct 10 ms 1496 KB Output is correct
9 Correct 9 ms 1576 KB Output is correct
10 Correct 8 ms 1496 KB Output is correct
11 Incorrect 9 ms 1496 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 10 ms 1496 KB Output is correct
8 Correct 10 ms 1496 KB Output is correct
9 Correct 9 ms 1576 KB Output is correct
10 Correct 8 ms 1496 KB Output is correct
11 Incorrect 9 ms 1496 KB Output isn't correct
12 Halted 0 ms 0 KB -