Submission #1102238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102238		imarn	Nile (IOI24_nile)	C++17	100 / 100	92 ms	14052 KiB

nile

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
using namespace std;
const int mxn=1e5+5;
int mx[mxn]{0},sz[mxn]{0},pr[mxn]{0};
int vl[mxn][2]{0};
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
int cal(int u){
    if(sz[u]%2==0)return 0;
    return max(vl[u][u&1],mx[u]);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,std::vector<int> B, std::vector<int> E){
    vector<pair<int,pii>>v;int n=W.size(),m=E.size();
    for(int i=0;i<n;i++)v.pb({W[i],{A[i],B[i]}});sort(all(v));
    for(int i=0;i<n;i++)W[i]=v[i].f,A[i]=v[i].s.f,B[i]=v[i].s.s;
    vector<pii>q1,q2;for(int i=0;i<n;i++)pr[i]=i,sz[i]=1,vl[i][i&1]=B[i]-A[i],mx[i]=-2e9,vl[i][(i+1)&1]=-2e9;
    for(int i=0;i<n-1;i++)q1.pb({W[i+1]-W[i],i});
    for(int i=1;i<n-1;i++)q2.pb({W[i+1]-W[i-1],i});
    sort(all(q1));sort(all(q2));
    ll rs=0;for(int i=0;i<n;i++)rs+=A[i];
    vector<pii>qr;for(int i=0;i<m;i++)qr.pb({E[i],i});
    sort(all(qr));int id1=0,id2=0;
    vector<ll>res(m,0);
    for(auto [d,i]:qr){
        while(id1<q1.size()&&q1[id1].f<=d){
            int u=get(q1[id1].s);
            int v=get(q1[id1].s+1);
            rs+=cal(u);
            rs+=cal(v);
            pr[u]=v;
            sz[v]+=sz[u];
            vl[v][0]=max(vl[v][0],vl[u][0]);
            vl[v][1]=max(vl[v][1],vl[u][1]);
            mx[v]=max(mx[v],mx[u]);
            rs-=cal(v);id1++;
        }
        while(id2<q2.size()&&q2[id2].f<=d){
            int u=get(q2[id2].s);
            rs+=cal(u);
            mx[u]=max(mx[u],B[q2[id2].s]-A[q2[id2].s]);
            rs-=cal(u);id2++;
        }
        res[i]=rs;
    }
    return res;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:26:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   26 |     for(int i=0;i<n;i++)v.pb({W[i],{A[i],B[i]}});sort(all(v));
      |     ^~~
nile.cpp:26:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   26 |     for(int i=0;i<n;i++)v.pb({W[i],{A[i],B[i]}});sort(all(v));
      |                                                  ^~~~
nile.cpp:37: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]
   37 |         while(id1<q1.size()&&q1[id1].f<=d){
      |               ~~~^~~~~~~~~~
nile.cpp:49: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]
   49 |         while(id2<q2.size()&&q2[id2].f<=d){
      |               ~~~^~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18