oj.uz

Submission #933529

# Submission time Handle Problem Language Result Execution time Memory
933529 2024-02-25T21:05:59 Z Hanksburger Examination (JOI19_examination) C++17
0 / 100
 380 ms 19400 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int, int>, pair<int, int> > > vec;
int bit[600005], ans[100005];
map<int, int> mp;
void upd(int x, int y)
{
    for (int i=x; i<=6e5; i+=i&(-i))
        bit[i]+=y;
}
int qry(int x)
{
    int res=0;
    for (int i=x; i; i-=i&(-i))
        res+=bit[i];
    return res;
}
void recur(int l, int r)
{
    if (l==r)
        return;
    int mid=(l+r)/2;
    vector<pair<pair<int, int>, int> > a;
    vector<pair<int, int> > b;
    for (int i=l; i<=mid; i++)
        if (vec[i].first.second)
            a.push_back({vec[i].second, vec[i].first.second});
    for (int i=mid+1; i<=r; i++)
        if (!vec[i].first.second)
            b.push_back(vec[i].second);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int ind=b.size();
    for (int i=a.size()-1; i>=0; i--)
    {
        while (ind && b[ind-1].first>=a[i].first.first)
        {
            upd(6e5+1-b[ind-1].second, 1);
            ind--;
        }
        ans[a[i].second]+=qry(6e5+1-a[i].first.second);
    }
    for (int i=ind; i<b.size(); i++)
        upd(6e5+1-b[i].second, -1);
    recur(l, mid);
    recur(mid+1, r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, cnt=0;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        int x, y;
        cin >> x >> y;
        vec.push_back({{x+y, 0}, {x, y}});
        mp[x]=mp[y]=mp[x+y]=0;
    }
    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        vec.push_back({{z, i}, {x, y}});
        mp[x]=mp[y]=mp[z]=0;
    }
    for (auto it=mp.begin(); it!=mp.end(); it++)
        (*it).second=(++cnt);
    for (int i=0; i<vec.size(); i++)
    {
        vec[i].first.first=mp[vec[i].first.first];
        vec[i].second.first=mp[vec[i].second.first];
        vec[i].second.second=mp[vec[i].second.second];
    }
    sort(vec.begin(), vec.end());
    recur(0, vec.size()-1);
    for (int i=1; i<=m; i++)
        cout << ans[i] << '\n';
}

Compilation message

examination.cpp: In function 'void recur(int, int)':
examination.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=ind; i<b.size(); i++)
      |                     ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i=0; i<vec.size(); i++)
      |                   ~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 10 ms 1628 KB Output is correct
8 Correct 11 ms 1720 KB Output is correct
9 Correct 10 ms 1624 KB Output is correct
10 Correct 8 ms 1112 KB Output is correct
11 Correct 9 ms 1116 KB Output is correct
12 Incorrect 4 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 17316 KB Output is correct
2 Correct 380 ms 19040 KB Output is correct
3 Correct 371 ms 19400 KB Output is correct
4 Correct 260 ms 16568 KB Output is correct
5 Correct 296 ms 14452 KB Output is correct
6 Incorrect 150 ms 10948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 17316 KB Output is correct
2 Correct 380 ms 19040 KB Output is correct
3 Correct 371 ms 19400 KB Output is correct
4 Correct 260 ms 16568 KB Output is correct
5 Correct 296 ms 14452 KB Output is correct
6 Incorrect 150 ms 10948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 10 ms 1628 KB Output is correct
8 Correct 11 ms 1720 KB Output is correct
9 Correct 10 ms 1624 KB Output is correct
10 Correct 8 ms 1112 KB Output is correct
11 Correct 9 ms 1116 KB Output is correct
12 Incorrect 4 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -