제출 #1356121

#제출 시각아이디문제언어결과실행 시간메모리
1356121coin_Thumper (NOI25_thumper)C++20
100 / 100
463 ms68896 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
#define pb push_back
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        // code goes here
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> rab(n), delta(n);
        vector<pair<int, int>> u(n), v(n);
        for (int i = 0; i < n; i++){
            cin >> rab[i].fi >> rab[i].se;
            u[i].fi = rab[i].fi + rab[i].se;
            v[i].fi = rab[i].fi - rab[i].se;
            u[i].se = i;
            v[i].se = i;
        }

        vector<int> thumps(n, 0);
        for (int i = 0; i < m; i++){
            int a;
            cin >> a;
            thumps[a-1]++;
        }

        // calculate change of diag coord
        vector<pair<int, int>> u_sort = u;
        sort(u_sort.begin(), u_sort.end());
        vector<int> pref_u(n+1, 0);
        for (int i = 0; i < n; i++){
            pref_u[i+1] = pref_u[i] + thumps[u_sort[i].se];
        }

        for (int i = 0; i < n; i++){
            int lo = lower_bound(u_sort.begin(), u_sort.end(), make_pair(u[i].fi, -1LL)) - u_sort.begin();
            int hi = upper_bound(u_sort.begin(), u_sort.end(), make_pair(u[i].fi, n)) - u_sort.begin();
            delta[i].fi = 2 * (pref_u[lo] - pref_u[n] + pref_u[hi]);
        }

        vector<pair<int, int>> v_sort = v;
        sort(v_sort.begin(), v_sort.end());
        vector<int> pref_v(n+1, 0);
        for (int i = 0; i < n; i++){
            pref_v[i+1] = pref_v[i] + thumps[v_sort[i].se];
        }

        for (int i = 0; i < n; i++){
            int lo = lower_bound(v_sort.begin(), v_sort.end(), make_pair(v[i].fi, -1LL)) - v_sort.begin();
            int hi = upper_bound(v_sort.begin(), v_sort.end(), make_pair(v[i].fi, n)) - v_sort.begin();
            delta[i].se = 2 * (pref_v[lo] - pref_v[n] + pref_v[hi]);
        }

        for (int i = 0; i < n; i++){
            int dx = (delta[i].fi+delta[i].se)/2;
            int dy = (delta[i].fi-delta[i].se)/2;
            cout << rab[i].fi + dx << ' ' << rab[i].se + dy << endl;
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…