제출 #365466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365466		doowey	New Home (APIO18_new_home)	C++17	12 / 100	5001 ms	980012 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 5;
const int inf = (int)1e9;
map<int, int> cnt[N];
int x[N], t[N], a[N], b[N];

vector<int> cors;

struct lin{
    int tt;
    int lef;
    int rig;
    int dir;
    int val;
    int add;
    bool operator< (const lin &aq) const {
        return tt < aq.tt;
    }
};

int cur;

vector<lin> lis;

void segm(int li, int ri, int mod){
    lis.push_back({cur, li, (li + ri) / 2, 0, -li, mod});
    lis.push_back({cur, (li + ri) / 2, ri, 1, ri, mod});
    cors.push_back((li + ri) / 2);
}

void add(int typ, int v){
    cnt[typ][v] ++ ;
    auto it = cnt[typ].find(v);
    auto nx = it;
    auto pv = it;
    if(cnt[typ][v] == 1){
        nx ++ ;
    }
    pv -- ;
    segm(pv->fi, nx->fi, 1);
    segm(pv->fi, it->fi, 0);
    segm(it->fi, nx->fi, 0);
}

void del(int typ, int v){
    auto it = cnt[typ].find(v);
    auto nx = it;
    auto pv = it;
    if(cnt[typ][v] == 1){
        nx ++ ;
    }
    pv -- ;

    segm(pv->fi, it->fi, 1);
    segm(it->fi, nx->fi, 1);
    segm(pv->fi, nx->fi, 0);
    cnt[typ][v] -- ;
    if(cnt[typ][v] == 0){
        cnt[typ].erase(v);
    }
}

int xx[N];
int yr[N];

const int M = 6*N;
map<int, int> segt[M * 2][2];

int getid(int pp){
    return lower_bound(cors.begin(), cors.end(), pp) - cors.begin();
}

int m;

void update(int node, int cl, int cr, int tl, int tr,int dir, int v, int mode){
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(mode == 0){
            segt[node][dir][v] ++ ;
        }
        else{
            segt[node][dir][v] -- ;
            if(segt[node][dir][v] == 0){
                segt[node][dir].erase(v);
            }
        }
        return;
    }
    int mid = (cl + cr) / 2;
    update(node * 2, cl, mid, tl, tr, dir, v, mode);
    update(node * 2 + 1, mid + 1, cr, tl, tr, dir, v, mode);
}

int get(int node, int cl, int cr, int pos){
    int vl = 0;
    if(!segt[node][0].empty()){
        auto it = segt[node][0].end();
        -- it;
        vl = max(vl, (it->fi) + cors[pos]);
    }
    if(!segt[node][1].empty()){
        auto it = segt[node][1].end();
        -- it;
        vl = max(vl, (it->fi) - cors[pos]);
    }
    if(cl == cr) return vl;
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        return max(vl, get(node * 2, cl, mid, pos));
    else
        return max(vl, get(node * 2 + 1, mid + 1, cr, pos));

}

int soln[N];

int main(){
    fastIO;
    int n, k, q;
    cin >> n >> k >> q;
    vector<pii> eve;
    for(int i = 1; i <= n; i ++ ){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        x[i] *= 2;
        cors.push_back(x[i]);
        eve.push_back(mp(a[i], i));
        eve.push_back(mp(b[i] + 1, i));
    }
    vector<pii> ord;
    for(int i = 1; i <= q; i ++ ){
        cin >> xx[i] >> yr[i];
        xx[i] *= 2;
        cors.push_back(xx[i]);
        ord.push_back(mp(yr[i], i));
    }
    sort(ord.begin(), ord.end());
    sort(eve.begin(), eve.end());
    for(int i = 1; i <= k ; i ++ ){
        cnt[i][-inf] ++ ;
        cnt[i][inf] ++ ;
        segm(-inf, inf, 0);
    }
    for(int i = 0 ; i < eve.size(); i ++ ){
        cur = eve[i].fi;
        if(cur == a[eve[i].se]){
            add(t[eve[i].se], x[eve[i].se]);
        }
        else{
            del(t[eve[i].se], x[eve[i].se]);
        }
    }
    sort(cors.begin(), cors.end());
    cors.resize(unique(cors.begin(), cors.end()) - cors.begin());
    m = cors.size();
    int it = 0;
    int gq;
    for(int i = 0; i < q ; i ++ ){
        while(it < lis.size() && lis[it].tt <= ord[i].fi){
            update(1, 0, m - 1, getid(lis[it].lef), getid(lis[it].rig), lis[it].dir, lis[it].val, lis[it].add);
            it ++ ;
        }

        gq = get(1, 0, m - 1, getid(xx[ord[i].se]));
        gq /= 2;
        if(gq > (int)1e8){
            soln[ord[i].se] = -1;
        }
        else{
            soln[ord[i].se] = gq;
        }
    }
    for(int i = 1; i <= q; i ++ ){
        cout << soln[i] << "\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'int main()':
new_home.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for(int i = 0 ; i < eve.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
new_home.cpp:169:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<lin>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         while(it < lis.size() && lis[it].tt <= ord[i].fi){
      |               ~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20