oj.uz

Submission #933365

# Submission time Handle Problem Language Result Execution time Memory
933365 2024-02-25T14:57:35 Z Hanksburger Examination (JOI19_examination) C++17
2 / 100
 3000 ms 206704 KB 
#include <bits/stdc++.h>
using namespace std;
pair<pair<long long, long long>, pair<long long, long long> > b[100005];
pair<long long, pair<long long, long long> > a[100005];
map<pair<long long, long long>, long long> mp;
long long ans[100005];
void upd(long long x, long long y)
{
    for (long long i=x; i<=(1<<30); i+=i&(-i))
        for (long long j=y; j<=(1<<30); j+=j&(-j))
            mp[{i, j}]++;
}
long long qry(long long x, long long y)
{
    long long res=0;
    for (long long i=x; i; i-=i&(-i))
        for (long long j=y; j; j-=j&(-j))
            res+=mp[{i, j}];
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, ind;
    cin >> n >> m;
    for (long long i=1; i<=n; i++)
    {
        long long x, y;
        cin >> x >> y;
        a[i]={x+y+2, {x+1, y+1}};
    }
    for (long long i=1; i<=m; i++)
    {
        long long x, y, z;
        cin >> x >> y >> z;
        b[i]={{z+2, i}, {x+1, y+1}};
    }
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);
    ind=n;
    for (long long i=m; i>=1; i--)
    {
        while (ind && a[ind].first>=b[i].first.first)
        {
            upd(a[ind].second.first, a[ind].second.second);
            ind--;
        }
        ans[b[i].first.second]=qry(1<<30, 1<<30)-qry(1<<30, b[i].second.second-1)-qry(b[i].second.first-1, 1<<30)+qry(b[i].second.first-1, b[i].second.second-1);
    }
    for (long long i=1; i<=m; i++)
        cout << ans[i] << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 298 ms 90196 KB Output is correct
8 Correct 303 ms 90432 KB Output is correct
9 Correct 302 ms 90720 KB Output is correct
10 Correct 219 ms 63320 KB Output is correct
11 Correct 273 ms 63316 KB Output is correct
12 Correct 81 ms 4700 KB Output is correct
13 Correct 300 ms 90332 KB Output is correct
14 Correct 312 ms 89940 KB Output is correct
15 Correct 313 ms 90644 KB Output is correct
16 Correct 258 ms 63860 KB Output is correct
17 Correct 210 ms 63532 KB Output is correct
18 Correct 100 ms 4444 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 206704 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 3074 ms 206704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 298 ms 90196 KB Output is correct
8 Correct 303 ms 90432 KB Output is correct
9 Correct 302 ms 90720 KB Output is correct
10 Correct 219 ms 63320 KB Output is correct
11 Correct 273 ms 63316 KB Output is correct
12 Correct 81 ms 4700 KB Output is correct
13 Correct 300 ms 90332 KB Output is correct
14 Correct 312 ms 89940 KB Output is correct
15 Correct 313 ms 90644 KB Output is correct
16 Correct 258 ms 63860 KB Output is correct
17 Correct 210 ms 63532 KB Output is correct
18 Correct 100 ms 4444 KB Output is correct
19 Execution timed out 3074 ms 206704 KB Time limit exceeded
20 Halted 0 ms 0 KB -