oj.uz

Submission #522163

# Submission time Handle Problem Language Result Execution time Memory
522163 2022-02-04T02:44:21 Z phamhoanghiep Examination (JOI19_examination) C++14
0 / 100
 387 ms 24780 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct qry{
    int x,y,z;
    int id;
    qry (int _x, int _y, int _z, int _id): x(_x), y(_y), z(_z), id(_id) {};
};
bool cmp(qry q1, qry q2) {
    if(q1.x==q2.x) {
        if(q1.y==q2.y) {
            if(q1.z==q2.z) return q1.id>q2.id;
            return q1.z>q2.z;
        }
        return q1.y>q2.y;
    }
    return q1.x>q2.x;
}
vector<qry> vt;
int ans[maxn];
int S[maxn];
int T[maxn];
int X[maxn];
int Y[maxn];
int Z[maxn];
vector<int> val;
map<int,int> yay;
int n,q;
struct Binary_indexed_tree{
    int bit[2000000];
    int n;
    void init(int _n) {
        n=_n;
        for(int i=0 ; i<=n ; i++) bit[i]=0;
    }
    void upd(int pos, int val) {
        for(int i=pos ; i<=n ; i+=i&(-i)) bit[i]+=val;
    }
    int get_val(int pos) {
        int ans=0;
        for(int i=pos ; i>0 ; i-=i&(-i)) ans+=bit[i];
        return ans;
    }
}BIT;
void cdq(int l, int r) {
    if(l==r) return;
    int mid=(l+r)/2;
    cdq(l,mid); cdq(mid+1,r);
    int sum=0;
    int l_it=l;
    int r_it=mid+1;
    vector<int> record; // record the queries to reverse on BIT
    vector<qry> tmp; // for sorting according to y
    while(l_it<=mid&&r_it<=r) {
        if(vt[l_it].y>=vt[r_it].y) {
            if(!vt[l_it].id) {
                BIT.upd(vt[l_it].z,1);
                sum++;
                record.push_back(vt[l_it].z);
            }
            tmp.push_back(vt[l_it++]);
        }
        else {
            if(vt[r_it].id) {
                ans[vt[r_it].id]+=sum-BIT.get_val(vt[r_it].z-1);
            }
            tmp.push_back(vt[r_it++]);
        }
    }
    while(l_it<=mid) tmp.push_back(vt[l_it++]);
    while(r_it<=r) {
        if(vt[r_it].id) ans[vt[r_it].id]+=sum-BIT.get_val(vt[r_it].z-1);
        tmp.push_back(vt[r_it++]);
    }
    for(int i=l ; i<=r ; i++) vt[i]=tmp[i-l];
    for(int i: record) BIT.upd(i,-1);
    record.clear();
    tmp.clear();
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("draft.inp","r",stdin);
    //freopen("draft.out","w",stdout);
    cin>>n>>q;
    for(int i=1 ; i<=n ; i++) {
        cin>>S[i]>>T[i];
        val.push_back(S[i]);
        val.push_back(T[i]);
        val.push_back(S[i]+T[i]);
    }
    for(int i=1 ; i<=q ; i++) {
        cin>>X[i]>>Y[i]>>Z[i];
        val.push_back(X[i]);
        val.push_back(Y[i]);
        val.push_back(Z[i]);
    }
    sort(val.begin(),val.end());
    int cr=0;
    for(int i=0 ; i<val.size() ; i++) {
        if(!i||val[i]!=val[i-1]) {
            cr++;
            yay[val[i]]=cr;
        }
    }
    BIT.init(cr+5);
    for(int i=1 ; i<=n ; i++) {
        vt.push_back(qry(yay[S[i]],yay[T[i]],yay[S[i]+T[i]],0));
    }
    for(int i=1 ; i<=q ; i++) {
        vt.push_back(qry(yay[X[i]],yay[Y[i]],yay[Z[i]],i));
    }
    sort(vt.begin(),vt.end(),&cmp);
    cdq(0,n+q-1);
    for(int i=1 ; i<=q ; i++) {
        cout<<ans[i]<<'\n';
    }
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0 ; i<val.size() ; i++) {
      |                   ~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 12 ms 1728 KB Output is correct
8 Correct 12 ms 1740 KB Output is correct
9 Correct 11 ms 1724 KB Output is correct
10 Correct 9 ms 1484 KB Output is correct
11 Correct 9 ms 1456 KB Output is correct
12 Incorrect 5 ms 836 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 22308 KB Output is correct
2 Correct 380 ms 24780 KB Output is correct
3 Correct 383 ms 24748 KB Output is correct
4 Correct 295 ms 22052 KB Output is correct
5 Correct 287 ms 21880 KB Output is correct
6 Incorrect 146 ms 16520 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 22308 KB Output is correct
2 Correct 380 ms 24780 KB Output is correct
3 Correct 383 ms 24748 KB Output is correct
4 Correct 295 ms 22052 KB Output is correct
5 Correct 287 ms 21880 KB Output is correct
6 Incorrect 146 ms 16520 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 12 ms 1728 KB Output is correct
8 Correct 12 ms 1740 KB Output is correct
9 Correct 11 ms 1724 KB Output is correct
10 Correct 9 ms 1484 KB Output is correct
11 Correct 9 ms 1456 KB Output is correct
12 Incorrect 5 ms 836 KB Output isn't correct
13 Halted 0 ms 0 KB -