제출 #1163053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163053		modwwe	Tree (IOI24_tree)	C++20	컴파일 에러	0 ms	0 KiB

tree

//#include "park.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e18;
const int mod2 = 1e9+7;
//const int base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
ll kk;
ll el = 19;
main()
{
    ///top1tst
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    ///top1tst
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    ///top1tst
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
//   cin>>s1;
    // int t;cin>>t;while(t--)
    phongbeo();
    checktime
    ///top1tst
}
vector<int> a,b,costa,costb;
int cd[500001],prea[500001],preb[500001],d[500001],demc[500001],phai[500001],trai[500001];
void del(int x,int y);
struct segtree
{
    int t[200001];
    int lazy[200001][2];
    int total[200001];
    int g[200001][2];
    void apply(int node,int x,int y)
    {
        t[node]+=x;
        lazy[node][y]+=x;
        g[node][y]+=x;
        total[node]=max({total[node],t[node],g[node][y]});
    }
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            for(int j=0; j<2; j++)
                apply(i,lazy[x][j],j);
        lazy[x][0]=lazy[x][1]=0;
    }
    void build(int node,int l,int r)
    {
        g[node][0]=g[node][1]=-inf;
        lazy[node][0]=lazy[node][1]=0;
        if(l==r)
        {
            demc[l]=0;
            t[node]=cd[l]-preb[d[a[l]]];
            total[node]=t[node];
            return;
        }
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        t[node]=max(t[node<<1],t[node<<1|1]);
        total[node]=max(total[node<<1],total[node<<1|1]);
    }
    void upd(int node,int l,int r,int l1,int r1,int x,int y)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            apply(node,x,y);
            return;
        }
        int mid=l+r>>1;
        if(lazy[node][0]!=0||lazy[node][1])ff(node);
        upd(node<<1,l,mid,l1,r1,x,y);
        upd(node<<1|1,mid+1,r,l1,r1,x,y);
        t[node]=max(t[node<<1],t[node<<1|1]);
        total[node]=max(total[node<<1],total[node<<1|1]);
        for(int j=0; j<2; j++)
            g[node][j]=max(g[node<<1][j],g[node<<1|1][j]);
    }
    void cc(int node,int l,int r,int l1,int x,int cost)
    {
        if(l==r)
        {
            demc[l]++;
            if(demc[l]==1)
            {
                g[node][1-x]=-inf;
                g[node][x]=t[node]+cost;
                total[node]=t[node]+cost;
            }
            t[node]=-inf;
            if(demc[l]==2)
                total[node]=prea[phai[l]-1]-prea[trai[l]]-preb[d[a[l]]],
                g[node][0]=g[node][1]=-inf;
            return;
        }
        int mid=l+r>>1;
        if(lazy[node]!=0)ff(node);
        if(l1<=mid)cc(node<<1,l,mid,l1,x,cost);
        else cc(node<<1|1,mid+1,r,l1,x,cost);
        t[node]=max(t[node<<1],t[node<<1|1]);
        total[node]=max(total[node<<1],total[node<<1|1]);
        for(int j=0; j<2; j++)
            g[node][j]=max(g[node<<1][j],g[node<<1|1][j]);
    }
} st;
int f[1000001],haha[1000001];
vector<int> rgt[1000001];
vector<int> lft[1000001];
set<int> s;
namespace dsuconcu
{
struct ie
{
    int a,b,l,r,cost;
};
struct ic
{
    int a,b,c;
};
ie dsu[100001];
ic maxx;
void reset()
{
    maxx= {0,0,0};
    for(int i=1; i<=n; i++)
        dsu[i]= {1,i,i,i,costa[i]};
}
int get(int x)
{
    if(dsu[x].b!=x)dsu[x].b=get(dsu[x].b);
    return dsu[x].b;
}
void noi(int x,int y)
{
    x=get(x);
    y=get(y);
    if(x==y)assert(0);
    if(dsu[x].a<dsu[y].a)swap(x,y);
    dsu[x].a+=dsu[y].a;
    dsu[y].b=x;
    dsu[x].cost+=dsu[y].cost;
    dsu[x].l=min(dsu[x].l,dsu[y].l);
    dsu[x].r=max(dsu[x].r,dsu[y].r);
    if(dsu[x].cost>maxx.a)
        maxx= {dsu[x].cost,dsu[x].l,dsu[x].r};
}
}
void solve()
{
    dsuconcu::reset();
    for(int i=1; i<=n; i++)
        prea[i]=prea[i-1]+costa[i];
    for(int i=1; i<=m; i++)
        preb[i]=preb[i-1]+costb[i],rgt[i].clear(),lft[i].clear();
    int pos;
    for(int i=1; i<=m; i++)
        if(preb[i]>preb[m]/2)
        {
            pos=i;
            break;
        }
    ///use pos
    memset(d,0,sizeof d);
    memset(f,0,sizeof f);
    memset(haha,0,sizeof haha);
    for(int i=1; i<=pos; i++)
        d[b[i]]=i;
    for(int i=1; i<=m; i++)haha[b[i]]=i;
    for(int i=1; i<=n+m; i++)
        f[i]=m;
    for(int i=pos+1; i<=m; i++)
        f[b[i]]=i-1;
    stack<int> ss;
    for(int i=1; i<=n; i++)
        phai[i]=n+1,trai[i]=0;
    for(int i=n; i>=1; --i)
    {
        if(f[a[i]]==m)
        {
            while(!ss.empty()&&d[a[i]]>d[a[ss.top()]])
            {
                s2=ss.top();
                ss.pop();
                if(!ss.empty())
                    f[a[ss.top()]]=min(f[a[s2]],f[a[ss.top()]]);
            }
            if(!ss.empty())rgt[f[a[ss.top()]]].pb(i),phai[i]=ss.top();
        }
        if(f[a[i]]==m)ss.push(i);
        else if(!ss.empty())f[a[ss.top()]]=min(f[a[ss.top()]],f[a[i]]);
    }
    while(!ss.empty())
        ss.pop();
    for(int i=1; i<=n+m; i++)
        f[i]=m;
    for(int i=pos+1; i<=m; i++)
        f[b[i]]=i-1;
    for(int i=1; i<=n; i++)
    {
        if(f[a[i]]==m)
        {
            while(!ss.empty()&&d[a[i]]>=d[a[ss.top()]])
            {
                s2=ss.top();
                ss.pop();
                if(!ss.empty())
                    f[a[ss.top()]]=min(f[a[s2]],f[a[ss.top()]]);
            }
            if(!ss.empty())lft[f[a[ss.top()]]].pb(i),trai[i]=ss.top();
        }
        if(f[a[i]]==m)ss.push(i);
        else if(!ss.empty())f[a[ss.top()]]=min(f[a[ss.top()]],f[a[i]]);
    }
    s.clear();
    s.insert(0);
    s.insert(n+1);
    for(int i=1; i<=n+m; i++)
        f[i]=0;
    for(int i=1; i<=n; i++)
    {
        if(haha[a[i]]>pos)s.insert(i);
        f[a[i]]=i;
    }
    for(int i=1; i<=n; i++)
    {
        cd[i]=-inf;
        if(haha[a[i]]<=pos)
        {
            auto it=s.lower_bound(i);
            s2=*it;
            if(s2>phai[i])s2=phai[i];
            it=prev(it);
            s3=*it;
            if(s3<trai[i])s3=trai[i];
            cd[i]=prea[s2-1]-prea[s3];
        }
    }
    st.build(1,1,n);
    for(int i=m; i>=pos; --i)
    {
        if(i!=m)
        {
            for(auto x:rgt[i])
            {
                s2=*s.lower_bound(x);
                st.cc(1,1,n,x,0,prea[phai[x]-1]-prea[s2-1]);
            }
            for(auto x:lft[i])
            {
                auto it=s.lower_bound(x);
                it=prev(it);
                s2=*it;
                st.cc(1,1,n,x,1,prea[s2]-prea[trai[x]]);
            }
            del(b[i+1],i+1);
        }
        else
        {
            for(auto x:rgt[i])
                st.cc(1,1,n,x,0,0);
            for(auto x:lft[i])
                st.cc(1,1,n,x,1,0);
        }
        s4=max({s4,preb[i]+st.total[1],preb[i]+dsuconcu::maxx.a});
    }
}
void del(int x,int y)
{
    if(f[x]==0) return;
    s.erase(f[x]);
    now=f[x];
    if(dsuconcu::maxx.a<costa[now])
        dsuconcu::maxx= {costa[now],now,now};
    if(haha[a[now-1]]>=y)dsuconcu::noi(now,now-1);
    if(now!=a.size()-1)
        if(haha[a[now+1]]>=y)dsuconcu::noi(now,now+1);
    int lc,rc;
    auto it=s.lower_bound(f[x]);
    rc=*it;
    it=prev(it);
    lc=*it;
    st.upd(1,1,n,lc+1,f[x]-1,prea[rc-1]-prea[f[x]-1],1);
    st.upd(1,1,n,f[x]+1,rc-1,prea[f[x]]-prea[lc],0);
}
void phongbeo()
{
    cin>>n>>m;
    a.resize(n+1);
    b.resize(m+1);
    costa.resize(n+1);
    costb.resize(m+1);
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++)
        cin>>costa[i];
    for(int i=1; i<=m; i++)
        cin>>b[i];
    for(int i=1; i<=m; i++)
        cin>>costb[i];
   solve();
    swap(a,b);
    swap(costa,costb);
    swap(n,m);
    solve();
    cout<<s4;
    ///    cout<<ans[0]<<" "<<ans[1]<<"\n";
    /// cout<<ans[2]<<" "<<ans[3]<<"\n";
}

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

tree.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~
tree.cpp: In function 'int main()':
tree.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
tree.cpp:38:9: note: in expansion of macro 'fin'
   38 |         fin(task2);
      |         ^~~
tree.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
tree.cpp:39:9: note: in expansion of macro 'fou'
   39 |         fou(task2);
      |         ^~~
tree.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
tree.cpp:44:9: note: in expansion of macro 'fin'
   44 |         fin(task);
      |         ^~~
tree.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
tree.cpp:45:9: note: in expansion of macro 'fou'
   45 |         fou(task);
      |         ^~~
/usr/bin/ld: /tmp/ccVb1V1t.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJQctaN.o:tree.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVb1V1t.o: in function `main':
grader.cpp:(.text.startup+0x2fd): undefined reference to `init(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x3c2): undefined reference to `query(int, int)'
collect2: error: ld returned 1 exit status