Submission #477807

#	Time	Username	Problem	Language	Result	Execution time	Memory
477807		Rainbowbunny	Examination (JOI19_examination)	C++17	100 / 100	722 ms	54340 KiB

examination

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5 + 5;
 
struct Data
{
    int s, t, sum, id;
    Data(int s = 0, int t = 0, int sum = 0, int id = 0) : s(s), t(t), sum(sum), id(id) {}
};
 
int n, q;
int ans[MAXN];
vector <int> S, T;
vector <int> Value[MAXN], BIT[MAXN];
vector <Data> Student, Query, Query2D;
 
void Unique(vector <int> &A)
{
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
}
 
void Change(vector <Data> &A)
{
    for(auto &x : A)
    {
        x.s = S.end() - lower_bound(S.begin(), S.end(), x.s);
        x.t = T.end() - lower_bound(T.begin(), T.end(), x.t);
    }
}
 
int GetPos(vector <int> &A, int b)
{
    return lower_bound(A.begin(), A.end(), b) - A.begin();
}
 
void FakeUpdate(int x, int y)
{
    for(x; x < MAXN; x += x & -x)
    {
        Value[x].push_back(y);
    }
}
 
void FakeGet(int x, int y)
{
    for(x; x > 0; x -= x & -x)
    {
        Value[x].push_back(y);
    }
}
 
void Update(int x, int y)
{
    for(x; x < MAXN; x += x & -x)
    {
        for(int id = GetPos(Value[x], y); id < (int)BIT[x].size(); id += id & -id)
        {
            BIT[x][id]++;
        }
    }
}
 
int Get(int x, int y)
{
    int ans = 0;
    for(x; x > 0; x -= x & -x)
    {
        for(int id = GetPos(Value[x], y); id > 0; id -= id & -id)
        {
            ans += BIT[x][id];
        }
    }
    return ans;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    Student.resize(n);
    for(int i = 0; i < n; i++)
    {
        cin >> Student[i].s >> Student[i].t;
        S.push_back(Student[i].s);
        T.push_back(Student[i].t);
        Student[i].sum = Student[i].s + Student[i].t;
        Student[i].id = -1;
    }
    Query.resize(q);
    for(int i = 0; i < q; i++)
    {
        cin >> Query[i].s >> Query[i].t >> Query[i].sum;
        S.push_back(Query[i].s);
        T.push_back(Query[i].t);
        Query[i].id = i;
    }
    sort(Student.begin(), Student.end(), [](Data A, Data B)
    {
        return A.sum > B.sum;
    });
    sort(Query.begin(), Query.end(), [](Data A, Data B)
    {
        return A.sum > B.sum;
    });
    Unique(S);
    Unique(T);
    Change(Student);
    Change(Query);
    int pt0 = 0, pt1 = 0;
    while(pt0 < (int)Student.size() and pt1 < (int)Query.size())
    {
        if(Student[pt0].sum >= Query[pt1].sum)
        {
            Query2D.push_back(Student[pt0]);
            pt0++;
        }
        else
        {
            Query2D.push_back(Query[pt1]);
            pt1++;
        }
    }
    while(pt1 < (int)Query.size())
    {
        Query2D.push_back(Query[pt1]);
        pt1++;
    }
    for(auto x : Query2D)
    {
        if(x.id == -1)
        {
            FakeUpdate(x.s, x.t);
        }
        else
        {
            FakeGet(x.s, x.t);
        }
    }
    for(int i = 1; i < MAXN; i++)
    {
        Value[i].push_back(0);
        Unique(Value[i]);
        BIT[i].resize(Value[i].size() + 5);
    }
    for(auto x : Query2D)
    {
        if(x.id == -1)
        {
            Update(x.s, x.t);
        }
        else
        {
            ans[x.id] = Get(x.s, x.t);
        }
    }
    for(int i = 0; i < q; i++)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

examination.cpp: In function 'void FakeUpdate(int, int)':
examination.cpp:40:9: warning: statement has no effect [-Wunused-value]
   40 |     for(x; x < MAXN; x += x & -x)
      |         ^
examination.cpp: In function 'void FakeGet(int, int)':
examination.cpp:48:9: warning: statement has no effect [-Wunused-value]
   48 |     for(x; x > 0; x -= x & -x)
      |         ^
examination.cpp: In function 'void Update(int, int)':
examination.cpp:56:9: warning: statement has no effect [-Wunused-value]
   56 |     for(x; x < MAXN; x += x & -x)
      |         ^
examination.cpp: In function 'int Get(int, int)':
examination.cpp:68:9: warning: statement has no effect [-Wunused-value]
   68 |     for(x; x > 0; x -= x & -x)
      |         ^

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57