oj.uz

Submission #477805

# Submission time Handle Problem Language Result Execution time Memory
477805 2021-10-04T00:08:31 Z Rainbowbunny Examination (JOI19_examination) C++17
2 / 100
 3000 ms 36176 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 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() + 1);
    }
    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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11408 KB Output is correct
2 Correct 16 ms 11216 KB Output is correct
3 Correct 16 ms 11164 KB Output is correct
4 Correct 15 ms 11288 KB Output is correct
5 Correct 16 ms 11240 KB Output is correct
6 Correct 15 ms 11264 KB Output is correct
7 Correct 38 ms 12104 KB Output is correct
8 Correct 36 ms 12104 KB Output is correct
9 Correct 48 ms 12008 KB Output is correct
10 Correct 28 ms 11840 KB Output is correct
11 Correct 53 ms 12192 KB Output is correct
12 Correct 22 ms 11856 KB Output is correct
13 Correct 37 ms 12060 KB Output is correct
14 Correct 40 ms 12068 KB Output is correct
15 Correct 38 ms 12060 KB Output is correct
16 Correct 45 ms 12032 KB Output is correct
17 Correct 24 ms 11896 KB Output is correct
18 Correct 21 ms 11788 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 36176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 36176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11408 KB Output is correct
2 Correct 16 ms 11216 KB Output is correct
3 Correct 16 ms 11164 KB Output is correct
4 Correct 15 ms 11288 KB Output is correct
5 Correct 16 ms 11240 KB Output is correct
6 Correct 15 ms 11264 KB Output is correct
7 Correct 38 ms 12104 KB Output is correct
8 Correct 36 ms 12104 KB Output is correct
9 Correct 48 ms 12008 KB Output is correct
10 Correct 28 ms 11840 KB Output is correct
11 Correct 53 ms 12192 KB Output is correct
12 Correct 22 ms 11856 KB Output is correct
13 Correct 37 ms 12060 KB Output is correct
14 Correct 40 ms 12068 KB Output is correct
15 Correct 38 ms 12060 KB Output is correct
16 Correct 45 ms 12032 KB Output is correct
17 Correct 24 ms 11896 KB Output is correct
18 Correct 21 ms 11788 KB Output is correct
19 Execution timed out 3075 ms 36176 KB Time limit exceeded
20 Halted 0 ms 0 KB -