제출 #728058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728058		Seb	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	718 ms	81448 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 2e5 + 5;
const ll INF = 1e16;

#define f first
#define s second

struct st{
ll ini,fin;
st *l,*r;
vector <ll> v;
st (ll INI, ll FIN) {
    ini = INI;
    fin = FIN;
    l = nullptr;
    r = nullptr;
}
};

pair <ll,ll> num[MAXN];
ll op[MAXN], act[MAXN], ans;

void setup(st *nodo) {
    if (nodo->ini==nodo->fin) {
        nodo->v.push_back(op[nodo->ini]);
        return;
    }
    nodo->l = new st(nodo->ini,(nodo->ini+nodo->fin)/2);
    nodo->r = new st((nodo->ini+nodo->fin)/2+1,nodo->fin);
    setup(nodo->l);
    setup(nodo->r);
    int i=0,j=0;
    while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
        if (nodo->l->v[i] > nodo->r->v[j]) {
            nodo->v.push_back(nodo->r->v[j]);
            j++;
        }
        else {
            nodo->v.push_back(nodo->l->v[i]);
            i++;
        }
    }
    while (i<nodo->l->v.size()) {
        nodo->v.push_back(nodo->l->v[i]);
        i++;
    }
    while (j<nodo->r->v.size()) {
        nodo->v.push_back(nodo->r->v[j]);
        j++;
    }
    return;
}

ll bin(st *nodo, ll ini, ll fin, ll x) {
    if (ini==fin) return ini;
    if (nodo->v[(ini+fin)/2] > x) return bin(nodo,ini,(ini+fin)/2,x);
    else return bin(nodo,(ini+fin)/2+1,fin,x);
}

ll query(st *nodo, ll L, ll R, ll x) {
    if (L>nodo->fin || nodo->ini>R) return 0;
    if (L<=nodo->ini && nodo->fin<=R) return bin(nodo,0,nodo->v.size(),x);
    return query(nodo->l,L,R,x) + query(nodo->r,L,R,x);
}

ll cami(st *nodo, ll x1, ll x2) {
    if (nodo->ini==nodo->fin) return nodo->ini;
    if (bin(nodo->r,0,nodo->r->v.size(),x2) - bin(nodo->r,0,nodo->r->v.size(),x1-1) > 0) return cami(nodo->r,x1,x2);
    else return cami(nodo->l,x1,x2);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,k,in;
cin>>n>>k;
for (int i=0;i<n;i++) {
    cin>>num[i].f>>num[i].s;
    act[i] = num[i].f;
    if (num[i].f>num[i].s) swap(num[i].f,num[i].s);
}
for (int i=0;i<k;i++) cin>>op[i];
st *nodo = new st(0,k-1);
setup(nodo);
for (int i=0;i<n;i++) {
    if (bin(nodo,0,nodo->v.size(),num[i].s-1) - bin(nodo,0,nodo->v.size(),num[i].f-1) > 0) {
        act[i] = num[i].s;
        in = cami(nodo,num[i].f,num[i].s-1) + 1;
    }
    else in = 0;
    if ((k-in-query(nodo,in,k-1,num[i].f-1))%2==1) {
        if (act[i]==num[i].f) act[i] = num[i].s;
        else act[i] = num[i].f;
    }
    ans += act[i];
}
cout<<ans;
return 0;
}

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

fortune_telling2.cpp: In function 'void setup(st*)':
fortune_telling2.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
      |            ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:38:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
      |                                   ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (i<nodo->l->v.size()) {
      |            ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while (j<nodo->r->v.size()) {
      |            ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65