oj.uz

Submission #933531

# Submission time Handle Problem Language Result Execution time Memory
933531 2024-02-25T21:06:54 Z Hanksburger Examination (JOI19_examination) C++17
0 / 100
 438 ms 28072 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<long long, long long>, pair<long long, long long> > > vec;
long long bit[600005], ans[100005];
map<long long, long long> mp;
void upd(long long x, long long y)
{
    for (long long i=x; i<=6e5; i+=i&(-i))
        bit[i]+=y;
}
long long qry(long long x)
{
    long long res=0;
    for (long long i=x; i; i-=i&(-i))
        res+=bit[i];
    return res;
}
void recur(long long l, long long r)
{
    if (l==r)
        return;
    long long mid=(l+r)/2;
    vector<pair<pair<long long, long long>, long long> > a;
    vector<pair<long long, long long> > b;
    for (long long i=l; i<=mid; i++)
        if (vec[i].first.second)
            a.push_back({vec[i].second, vec[i].first.second});
    for (long long 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());
    long long ind=b.size();
    for (long long 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 (long long 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);
    long long n, m, cnt=0;
    cin >> n >> m;
    for (long long i=1; i<=n; i++)
    {
        long long x, y;
        cin >> x >> y;
        vec.push_back({{x+y, 0}, {x, y}});
        mp[x]=mp[y]=mp[x+y]=0;
    }
    for (long long i=1; i<=m; i++)
    {
        long long 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 (long long 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 (long long i=1; i<=m; i++)
        cout << ans[i] << '\n';
}

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 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 11 ms 2008 KB Output is correct
8 Correct 11 ms 2108 KB Output is correct
9 Correct 12 ms 2112 KB Output is correct
10 Correct 9 ms 1496 KB Output is correct
11 Correct 9 ms 1496 KB Output is correct
12 Incorrect 4 ms 860 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 28072 KB Output is correct
2 Correct 438 ms 26748 KB Output is correct
3 Correct 383 ms 25772 KB Output is correct
4 Correct 266 ms 23908 KB Output is correct
5 Correct 313 ms 23552 KB Output is correct
6 Incorrect 151 ms 17660 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 28072 KB Output is correct
2 Correct 438 ms 26748 KB Output is correct
3 Correct 383 ms 25772 KB Output is correct
4 Correct 266 ms 23908 KB Output is correct
5 Correct 313 ms 23552 KB Output is correct
6 Incorrect 151 ms 17660 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 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 11 ms 2008 KB Output is correct
8 Correct 11 ms 2108 KB Output is correct
9 Correct 12 ms 2112 KB Output is correct
10 Correct 9 ms 1496 KB Output is correct
11 Correct 9 ms 1496 KB Output is correct
12 Incorrect 4 ms 860 KB Output isn't correct
13 Halted 0 ms 0 KB -