oj.uz

답안 #369647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369647 2021-02-22T07:20:32 Z CodePlatina Examination (JOI19_examination) C++14
41 / 100
 351 ms 29280 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define tlll tuple<long long, long long, long long>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

int ps[101010];
vector<int> prX;
vector<int> prY;
vector<int> prP;
vector<tiii> lsX[101010];
vector<int> pntX[101010];
vector<tiii> lsPX[101010];
vector<int> pntPX[101010];
vector<tiii> lsPY[101010];
vector<int> pntPY[101010];

int N;
int ind[202020];
void init(void)
{
    for(int i = 0; i < 202020; ++i)
        ind[i] = 0;
}
void upd(int pos)
{
    pos += N;
    ++ind[pos];
    while(pos >>= 1) ++ind[pos];
}
int qr(int l, int r)
{
    int ret = 0;
    for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
    {
        if(x & 1) ret += ind[x++];
        if(y & 1) ret += ind[--y];
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T; cin >> n >> T;
    pii A[n]; tiii B[T];
    for(auto &i : A) cin >> i.ff >> i.ss;
    for(auto &[a, b, c] : B) cin >> a >> b >> c;

    for(auto &i : A)
    {
        prX.push_back(i.ff);
        prY.push_back(i.ss);
        prP.push_back(i.ff + i.ss);
    }

    sort(prX.begin(), prX.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    sort(prY.begin(), prY.end());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());
    sort(prP.begin(), prP.end());
    prP.resize(unique(prP.begin(), prP.end()) - prP.begin());

    for(auto &i : A)
    {
        int x = lower_bound(prX.begin(), prX.end(), i.ff) - prX.begin();
        int y = lower_bound(prY.begin(), prY.end(), i.ss) - prY.begin();
        int p = lower_bound(prP.begin(), prP.end(), i.ff + i.ss) - prP.begin();
        ++ps[p];
        pntX[x].push_back(y);
        pntPX[x].push_back(p);
        pntPY[y].push_back(p);
    }
    for(int i = (int)prP.size() - 2; i >= 0; --i) ps[i] += ps[i + 1];

    int ans[T]{};
    for(int i = 0; i < T; ++i)
    {
        auto [a, b, c] = B[i];

        int x = lower_bound(prX.begin(), prX.end(), a) - prX.begin();
        int y = lower_bound(prY.begin(), prY.end(), b) - prY.begin();
        int p = lower_bound(prP.begin(), prP.end(), c) - prP.begin();

        if(c <= a + b)
        {
            lsX[x].push_back({i, y, (int)prY.size()});
        }
        else
        {
            lsPX[x].push_back({i, p, (int)prP.size()});
            lsPY[y].push_back({i, p, (int)prP.size()});
            ans[i] = ps[p];
        }
    }

    N = prY.size();
    for(int i = (int)prX.size() - 1; i >= 0; --i)
    {
        for(auto j : pntX[i]) upd(j);
        for(auto [j, l, r] : lsX[i]) ans[j] += qr(l, r);
    }

    N = prP.size();
    init();
    for(int i = 0; i < (int)prP.size(); ++i)
    {
        for(auto [j, l, r] : lsPX[i]) ans[j] -= qr(l, r);
        for(auto j : pntPX[i]) upd(j);
    }

    init();
    for(int i = 0; i < (int)prP.size(); ++i)
    {
        for(auto [j, l, r] : lsPY[i]) ans[j] -= qr(l, r);
        for(auto j : pntPY[i]) upd(j);
    }

    for(int i = 0; i < T; ++i) cout << ans[i] << '\n';
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:65:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto &[a, b, c] : B) cin >> a >> b >> c;
      |               ^
examination.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |         auto [a, b, c] = B[i];
      |              ^
examination.cpp:118:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |         for(auto [j, l, r] : lsX[i]) ans[j] += qr(l, r);
      |                  ^
examination.cpp:125:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |         for(auto [j, l, r] : lsPX[i]) ans[j] -= qr(l, r);
      |                  ^
examination.cpp:132:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |         for(auto [j, l, r] : lsPY[i]) ans[j] -= qr(l, r);
      |                  ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15340 KB Output is correct
2 Correct 13 ms 15340 KB Output is correct
3 Correct 12 ms 15340 KB Output is correct
4 Correct 11 ms 15340 KB Output is correct
5 Correct 11 ms 15404 KB Output is correct
6 Incorrect 11 ms 15340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 27708 KB Output is correct
2 Correct 319 ms 27744 KB Output is correct
3 Correct 314 ms 27744 KB Output is correct
4 Correct 204 ms 26220 KB Output is correct
5 Correct 176 ms 24672 KB Output is correct
6 Correct 104 ms 23440 KB Output is correct
7 Correct 291 ms 27752 KB Output is correct
8 Correct 314 ms 27744 KB Output is correct
9 Correct 289 ms 27744 KB Output is correct
10 Correct 158 ms 24156 KB Output is correct
11 Correct 194 ms 26044 KB Output is correct
12 Correct 71 ms 21852 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 27708 KB Output is correct
2 Correct 319 ms 27744 KB Output is correct
3 Correct 314 ms 27744 KB Output is correct
4 Correct 204 ms 26220 KB Output is correct
5 Correct 176 ms 24672 KB Output is correct
6 Correct 104 ms 23440 KB Output is correct
7 Correct 291 ms 27752 KB Output is correct
8 Correct 314 ms 27744 KB Output is correct
9 Correct 289 ms 27744 KB Output is correct
10 Correct 158 ms 24156 KB Output is correct
11 Correct 194 ms 26044 KB Output is correct
12 Correct 71 ms 21852 KB Output is correct
13 Correct 346 ms 29152 KB Output is correct
14 Correct 331 ms 28512 KB Output is correct
15 Correct 304 ms 27816 KB Output is correct
16 Correct 249 ms 27360 KB Output is correct
17 Correct 212 ms 25824 KB Output is correct
18 Correct 92 ms 23136 KB Output is correct
19 Correct 351 ms 29152 KB Output is correct
20 Correct 347 ms 28776 KB Output is correct
21 Correct 333 ms 29280 KB Output is correct
22 Correct 206 ms 23648 KB Output is correct
23 Correct 194 ms 25952 KB Output is correct
24 Correct 66 ms 21852 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15340 KB Output is correct
2 Correct 13 ms 15340 KB Output is correct
3 Correct 12 ms 15340 KB Output is correct
4 Correct 11 ms 15340 KB Output is correct
5 Correct 11 ms 15404 KB Output is correct
6 Incorrect 11 ms 15340 KB Output isn't correct
7 Halted 0 ms 0 KB -