Submission #1157092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157092		modwwe	Tricks of the Trade (CEOI23_trade)	C++20	40 / 100	8090 ms	26352 KiB

trade

//#include "grader.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 "ftree"
#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) (1<<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 = 1e16;
const ll mod2 = 1e9+7;
const ll base=67;
int  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;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9;
int kk;
int t;
int el = 19;
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    // ios_base::sync_with_stdio(0);
    //cout.tie(0);
    //cin.tie(0);
    /// cin>>s1;
//int t;cin>>t; while(t--)
    phongbeo();
    checktime
}
multiset<int> in,ou;
int a[250001];
int b[250001],dp[250001];
bool c[250001];
struct fenwick
{
    int t[1000001];
    void upd(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1||t[node]<x) return;
        if(l>=l1&&r<=r1)
        {
            t[node]=min(t[node],x);
            return;
        }
        int mid=l+r>>1;
        upd(node<<1,l,mid,l1,r1,x);
        upd(node<<1|1,mid+1,r,l1,r1,x);
    }
    void get(int node,int l,int r)
    {
        t[node]=min(t[node],t[node>>1]);
        if(l==r)
        {
            if(b[l]>=t[node])c[l]=1;
            return;
        }
        int mid=l+r>>1;
        get(node<<1,l,mid);
        get(node<<1|1,mid+1,r);
    }
} fen;
void add(int x)
{
    in.insert(x);
    s4+=x;
    if(in.size()==k+1)
    {
        s2=*in.begin();
        s4-=s2;
        in.erase(in.begin());
        ou.insert(s2);
    }
}
void del(int x)
{
    if(in.find(x)!=in.end())
    {
        in.erase(in.find(x));
        s4-=x;
        if(ou.size()!=0)
        {
            s2=*ou.rbegin();
            s4+=s2;
            in.insert(s2);
            ou.erase(ou.find(s2));
        }
    }
    else
    {
        if(ou.find(x)==ou.end())assert(0);
        ou.erase(ou.find(x));
    }
}
void go(int x,int y)
{
    while(l>x)
    {
        l--;
        add(b[l]);
    }
    while(r<y)
    {
        r++;
        add(b[r]);
    }
    while(r>y)
    {
        del(b[r]);
        r--;
    }
    while(l<x)
    {
        del(b[l]);
        l++;
    }
}
void dnc(int l,int r,int u,int v)
{
    if(l>r) return;
    int mid=l+r>>1;
    int pos=-1;
    if(mid-u<k-1)
    {
        dnc(mid+1,r,u,v);
        return;
    }
    dp[mid]=-inf;
    for(int i=u; i<=v; i++)
    {
        if(mid-i<k-1)break;
        go(i,mid);
        if(s4-(a[mid]-a[i-1])>dp[mid])
        {
            dp[mid]=s4-(a[mid]-a[i-1]);
            pos=i;
        }
    }
    s5=max(s5,dp[mid]);
    dnc(l,mid-1,u,pos);
    dnc(mid+1,r,pos,v);
}
void dnc2(int l,int r,int u,int v)
{
    if(u>v) return;
    if(l>r) return;
    int mid=l+r>>1;
    int pos=-1;
    if(mid-u<k-1)
    {
        dnc2(mid+1,r,u,v);
        return;
    }
    dp[mid]=-inf;
    for(int i=u; i<=v; i++)
    {
        if(mid-i<k-1)break;
        go(i,mid);
        if(s4-(a[mid]-a[i-1])>=dp[mid])
        {
            dp[mid]=s4-(a[mid]-a[i-1]);
            pos=i;
        }
        if(s4-(a[mid]-a[i-1])==s5)
        {
            // fen.upd(1,1,n,i,mid,*in.begin());
        }
    }
    s5=max(s5,dp[mid]);
    dnc2(mid+1,r,pos+1,v);
    dnc2(l,mid-1,u,pos);
}
void dnc3(int l,int r,int u,int v)
{
    if(l>r) return;
    int mid=l+r>>1;
    int pos=-1;
    if(mid-u<k-1)
    {
        dnc3(mid+1,r,u,v);
        return;
    }
    dp[mid]=-inf;
    for(int i=u; i<=v; i++)
    {
        if(mid-i<k-1)break;
        go(i,mid);
        if(s4-(a[mid]-a[i-1])>dp[mid])
        {
            dp[mid]=s4-(a[mid]-a[i-1]);
            pos=i;
        }
        if(s4-(a[mid]-a[i-1])==s5)
        {
            fen.upd(1,1,n,i,mid,*in.begin());
        }
    }
    dnc3(l,mid-1,u,pos);
    dnc3(mid+1,r,pos,v);
}
void phongbeo()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        cin>>a[i],dp[i]=-inf;
    for(int i=0; i<=4*n; i++)
        fen.t[i]=inf;
    for(int i=1; i<=n; i++)
        cin>>b[i];
    for(int i=1; i<=n; i++)
        a[i]+=a[i-1];
    l=1;
    r=0;
    s5=-inf;
    dnc(1,n,1,n);
    cout<<s5,down
        dnc2(1,n,1,n);
    dnc3(1,n,1,n);
    fen.get(1,1,n);
    for(int i=1; i<=n; i++)
        cout<<c[i];
}

Compilation message (stderr)

trade.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main()
      | ^~~~
trade.cpp: In function 'int main()':
trade.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
trade.cpp:38:9: note: in expansion of macro 'fin'
   38 |         fin(task2);
      |         ^~~
trade.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
trade.cpp:39:9: note: in expansion of macro 'fou'
   39 |         fou(task2);
      |         ^~~
trade.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
trade.cpp:43:9: note: in expansion of macro 'fin'
   43 |         fin(task);
      |         ^~~
trade.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
trade.cpp:44:9: note: in expansion of macro 'fou'
   44 |         fou(task);
      |         ^~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 25
• Subtask 5: 0 / 45