제출 #409593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409593		urd05	Construction of Highway (JOI18_construction)	C++14	16 / 100	2021 ms	25196 KiB

construction

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;

int n;
int arr[100000];
vector<int> adj[100000];
typedef pair<int,int> P;
P edge[100000];
int p[100000];
int ind[100000];
int siz[100000];
int f=0;
int depth[100000];
int par[100000][17];

void dfs(int v,int prev) {
    ind[v]=f++;
    siz[v]=1;
    p[v]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        depth[nt]=depth[v]+1;
        dfs(nt,v);
        siz[v]+=siz[nt];
    }
}

const int sz=131072;
P seg[sz*2];

P pmax(P a,P b) {
    return a<b?b:a;
}

P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return P(0,0);
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return pmax(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,P val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=pmax(seg[i*2],seg[i*2+1]);
    }
}

struct SegmentTree {
    vector<int> seg;
    int sz=1;
    void init(int x) {
        seg.resize(x+1);
        sz=x;
    }
    int sum(int i) {
        int ret=0;
        while (i>0) {
            assert(i<seg.size());
            ret+=seg[i];
            i-=(i&-i);
        }
        return ret;
    }
    void update(int i,int val) {
        while (i<=sz) {
            assert(i<seg.size());
            seg[i]+=val;
            i+=(i&-i);
        }
    }
};

long long cntinv(vector<P> v) {
    vector<int> press;
    press.push_back(-1);
    for(int i=0;i<v.size();i++) {
        //printf("%d %d\n",v[i].first,v[i].second);
        press.push_back(v[i].first);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    SegmentTree st;
    st.init(press.size());
    long long ret=0;
    for(int i=0;i<v.size();i++) {
        v[i].first=lower_bound(press.begin(),press.end(),v[i].first)-press.begin();
        assert(v[i].first!=0);
        ret+=1LL*v[i].second*st.sum(v[i].first-1);
        st.update(v[i].first,v[i].second);
    }
    return ret;
}

int main(void) {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    vector<int> press;
    for(int i=0;i<n;i++) {
        press.push_back(arr[i]);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=0;i<n;i++) {
        arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        edge[i]=P(u,v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0,-1);
    memset(par,-1,sizeof(par));
    for(int i=0;i<n;i++) {
        par[i][0]=p[i];
    }
    for(int j=1;j<17;j++) {
        for(int i=0;i<n;i++) {
            if (par[i][j-1]!=-1) {
                par[i][j]=par[par[i][j-1]][j-1];
            }
        }
    }
    for(int i=1;i<n;i++) {
        int now=edge[i].first;
        vector<P> vec;
        while (now!=-1) {
            int rec=now;
            int deep=sum(ind[now],ind[now]+siz[now]-1).second;
            for(int j=16;j>=0;j--) {
                int nt=par[rec][j];
                if (nt==-1) {
                    continue;
                }
                if (sum(ind[nt],ind[nt]+siz[nt]-1).second==deep) {
                    rec=nt;
                }
            }
            vec.push_back(P(arr[deep],depth[now]-depth[rec]+1));
            now=p[rec];
        }
        update(ind[edge[i].second],P(i,edge[i].second));
        printf("%lld\n",cntinv(vec));
    }
}

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

construction.cpp: In function 'void dfs(int, int)':
construction.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from construction.cpp:5:
construction.cpp: In member function 'int SegmentTree::sum(int)':
construction.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             assert(i<seg.size());
      |                    ~^~~~~~~~~~~
construction.cpp: In member function 'void SegmentTree::update(int, int)':
construction.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             assert(i<seg.size());
      |                    ~^~~~~~~~~~~
construction.cpp: In function 'long long int cntinv(std::vector<std::pair<int, int> >)':
construction.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
construction.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
construction.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
construction.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84