oj.uz

Submission #1102330

# Submission time Handle Problem Language Result Execution time Memory
1102330 2024-10-18T02:34:59 Z modwwe Nile (IOI24_nile) C++17
100 / 100
 149 ms 24492 KB 
#include "nile.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int2 long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9')
    {
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}

void phongbeo();
const int inf=1e9;
const int mod2=998244353;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int2 a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2;
int  i,s10,s12;
int kk;
int el=29;

ic a[100001];
int stt[17][100001];
int2 ans[100001];
struct cmp3
{
    bool operator()(ic a,ic b)
    {
        return a.a<b.a;
    }
};
priority_queue<ic,vector<ic>,cmp3>p;
vector<ib> v;
bool cmp(ic a,ic b)
{
    return a.a<b.a;
}
bool cmp2(ib a,ib b)
{
    return a.a>b.a;
}
struct IT
{
    int t[400001];
    void build(int node,int l,int r)
    {
        if(l==r)
        {
            t[node]=a[l].b-a[l].c;
            return;
        }
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        t[node]=min(t[node<<1],t[node<<1|1]);
    }

    void upd(int node,int l,int r,int l1)
    {
        if(l==r)
        {
            t[node]=1e9;
            return;
        }
        int mid=l+r>>1;
        if(l1<=mid) upd(node<<1,l,mid,l1);
        else upd(node<<1|1,mid+1,r,l1);
        t[node]=min(t[node<<1],t[node<<1|1]);
    }
    int get(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return 1e9;
        if(l>=l1&&r<=r1) return t[node];
        int mid=l+r>>1;
        return min(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
} st;
struct fenwick
{
    int bit[100001];
    void upd(int x,int y)
    {
        for(x; x<=n; x+=x&-x)
            bit[x]=max(bit[x],y);
    }
    int get(int x)
    {
        int s=0;
        for(x; x; x-=x&-x)
            s=max(s,bit[x]);
        return s;
    }
} fen,fen2;
int gett(int l,int r)
{
    int s=st.get(1,1,n,l,r);
    int kk=r-l;
    for(int j=16; j>=1; --j)
        if(bit(kk,j))
            s=min(s,stt[j][l]),
            l+=(1<<j);
    return min(s,stt[1][l]);
}
int2 solve(int l,int r)
{
    if((r-l)%2==1)
    {
        return a[r].c-a[l-1].c;
    }
    return a[r].c-a[l-1].c+gett(l,r);
}
vector<long long>vv;
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
n=W.size();
m=E.size();
    for(int i=1; i<=n; i++)
        a[i].a=W[i-1];
    for(int i=1; i<=n; i++)
        a[i].b=A[i-1];
    for(int i=1; i<=n; i++)
        a[i].c=B[i-1];
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n; i++)
        stt[1][i]=a[i].b-a[i].c;
    for(int i=1; i<=m; i++)
    {
       l=E[i-1],v.pb({l,i});

    }
    sort(v.begin(),v.end(),cmp2);
    st.build(1,1,n);
    for(int i=1; i<n; i++)
        p.push({a[i+1].a-a[i].a,i,i+1});
    for(int i=1; i<n-1; i++)
        p.push({a[i+2].a-a[i].a,i,i+2});
    for(int i=1; i<=n; i++)
        a[i].c+=a[i-1].c;
    for(int i=2; i<17; i++)
        for(int j=1; j+(1<<i)-1<=n; j++)
            stt[i][j]=min(stt[i-1][j],stt[i-1][j+(1<<(i-1))]);
    s6=solve(1,n);
    for(auto f:v)
    {
        while(!p.empty()&&p.top().a>f.a)
        {
            ic x=p.top();
            if(x.c-x.b==2)
            {
                s4=fen.get(x.b)+1;
                s5=n-fen2.get(n-x.b+1);
                if(s5>=x.c)
                {
                    s6-=solve(s4,s5);
                    st.upd(1,1,n,x.b+1);
                    s6+=solve(s4,s5);
                }
            }
            else
            {
                s4=fen.get(x.b)+1;
                s5=n-fen2.get(n-x.c+1);
                s6-=solve(s4,s5);
                s6+=solve(s4,x.b)+solve(x.c,s5);
                fen.upd(x.c,x.b);
                fen2.upd(n-x.b+1,n-x.b);
            }
            p.pop();
        }
        ans[f.b]=s6;
    }
    for(int i=1; i<=m; i++)
       vv.pb(ans[i]);
        return vv;
    }

Compilation message

nile.cpp: In member function 'void IT::build(int, int, int)':
nile.cpp:99:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         int mid=l+r>>1;
      |                 ~^~
nile.cpp: In member function 'void IT::upd(int, int, int, int)':
nile.cpp:112:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid=l+r>>1;
      |                 ~^~
nile.cpp: In member function 'int IT::get(int, int, int, int, int)':
nile.cpp:121:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int mid=l+r>>1;
      |                 ~^~
nile.cpp: In member function 'void fenwick::upd(int, int)':
nile.cpp:130:13: warning: statement has no effect [-Wunused-value]
  130 |         for(x; x<=n; x+=x&-x)
      |             ^
nile.cpp: In member function 'int fenwick::get(int)':
nile.cpp:136:13: warning: statement has no effect [-Wunused-value]
  136 |         for(x; x; x-=x&-x)
      |             ^
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:175:23: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
  175 |        l=E[i-1],v.pb({l,i});
      |                       ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 3 ms 10832 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 3 ms 10832 KB Output is correct
6 Correct 2 ms 10832 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20944 KB Output is correct
2 Correct 56 ms 20928 KB Output is correct
3 Correct 56 ms 20920 KB Output is correct
4 Correct 48 ms 20820 KB Output is correct
5 Correct 52 ms 20928 KB Output is correct
6 Correct 48 ms 20924 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 21176 KB Output is correct
2 Correct 74 ms 20944 KB Output is correct
3 Correct 102 ms 21048 KB Output is correct
4 Correct 100 ms 21192 KB Output is correct
5 Correct 73 ms 21192 KB Output is correct
6 Correct 125 ms 21176 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 3 ms 10832 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 3 ms 10832 KB Output is correct
6 Correct 2 ms 10832 KB Output is correct
7 Correct 3 ms 10832 KB Output is correct
8 Correct 3 ms 10832 KB Output is correct
9 Correct 4 ms 10832 KB Output is correct
10 Correct 3 ms 10832 KB Output is correct
11 Correct 3 ms 11000 KB Output is correct
12 Correct 4 ms 10832 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 3 ms 10832 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 3 ms 10832 KB Output is correct
6 Correct 2 ms 10832 KB Output is correct
7 Correct 58 ms 20944 KB Output is correct
8 Correct 56 ms 20928 KB Output is correct
9 Correct 56 ms 20920 KB Output is correct
10 Correct 48 ms 20820 KB Output is correct
11 Correct 52 ms 20928 KB Output is correct
12 Correct 48 ms 20924 KB Output is correct
13 Correct 83 ms 21176 KB Output is correct
14 Correct 74 ms 20944 KB Output is correct
15 Correct 102 ms 21048 KB Output is correct
16 Correct 100 ms 21192 KB Output is correct
17 Correct 73 ms 21192 KB Output is correct
18 Correct 125 ms 21176 KB Output is correct
19 Correct 3 ms 10832 KB Output is correct
20 Correct 3 ms 10832 KB Output is correct
21 Correct 4 ms 10832 KB Output is correct
22 Correct 3 ms 10832 KB Output is correct
23 Correct 3 ms 11000 KB Output is correct
24 Correct 4 ms 10832 KB Output is correct
25 Correct 90 ms 21184 KB Output is correct
26 Correct 83 ms 20920 KB Output is correct
27 Correct 122 ms 21016 KB Output is correct
28 Correct 129 ms 21020 KB Output is correct
29 Correct 71 ms 21020 KB Output is correct
30 Correct 132 ms 21172 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 21176 KB Output is correct
2 Correct 74 ms 20944 KB Output is correct
3 Correct 102 ms 21048 KB Output is correct
4 Correct 100 ms 21192 KB Output is correct
5 Correct 73 ms 21192 KB Output is correct
6 Correct 125 ms 21176 KB Output is correct
7 Correct 115 ms 24240 KB Output is correct
8 Correct 101 ms 24128 KB Output is correct
9 Correct 134 ms 24348 KB Output is correct
10 Correct 130 ms 24236 KB Output is correct
11 Correct 132 ms 24236 KB Output is correct
12 Correct 121 ms 24248 KB Output is correct
13 Correct 129 ms 24448 KB Output is correct
14 Correct 85 ms 24300 KB Output is correct
15 Correct 134 ms 24244 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 3 ms 10832 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 10832 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 2 ms 10832 KB Output is correct
8 Correct 58 ms 20944 KB Output is correct
9 Correct 56 ms 20928 KB Output is correct
10 Correct 56 ms 20920 KB Output is correct
11 Correct 48 ms 20820 KB Output is correct
12 Correct 52 ms 20928 KB Output is correct
13 Correct 48 ms 20924 KB Output is correct
14 Correct 83 ms 21176 KB Output is correct
15 Correct 74 ms 20944 KB Output is correct
16 Correct 102 ms 21048 KB Output is correct
17 Correct 100 ms 21192 KB Output is correct
18 Correct 73 ms 21192 KB Output is correct
19 Correct 125 ms 21176 KB Output is correct
20 Correct 3 ms 10832 KB Output is correct
21 Correct 3 ms 10832 KB Output is correct
22 Correct 4 ms 10832 KB Output is correct
23 Correct 3 ms 10832 KB Output is correct
24 Correct 3 ms 11000 KB Output is correct
25 Correct 4 ms 10832 KB Output is correct
26 Correct 90 ms 21184 KB Output is correct
27 Correct 83 ms 20920 KB Output is correct
28 Correct 122 ms 21016 KB Output is correct
29 Correct 129 ms 21020 KB Output is correct
30 Correct 71 ms 21020 KB Output is correct
31 Correct 132 ms 21172 KB Output is correct
32 Correct 115 ms 24240 KB Output is correct
33 Correct 101 ms 24128 KB Output is correct
34 Correct 134 ms 24348 KB Output is correct
35 Correct 130 ms 24236 KB Output is correct
36 Correct 132 ms 24236 KB Output is correct
37 Correct 121 ms 24248 KB Output is correct
38 Correct 129 ms 24448 KB Output is correct
39 Correct 85 ms 24300 KB Output is correct
40 Correct 134 ms 24244 KB Output is correct
41 Correct 108 ms 24224 KB Output is correct
42 Correct 106 ms 24236 KB Output is correct
43 Correct 134 ms 24236 KB Output is correct
44 Correct 128 ms 24240 KB Output is correct
45 Correct 134 ms 24492 KB Output is correct
46 Correct 133 ms 24232 KB Output is correct
47 Correct 136 ms 24236 KB Output is correct
48 Correct 91 ms 24264 KB Output is correct
49 Correct 149 ms 24388 KB Output is correct