Submission #1128008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128008		modwwe	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	546 ms	147592 KiB

constellation3

#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 NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)9
#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 mp make_pair
#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 = 2e9;
const ll mod2 = 1e9+7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
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 ;
int kk;
int el = 19;
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    //modwwe
    phongbeo();
    // checktime
}
ib st[18][200001];
int par[18][200001],dp[200001],a[200001],in[200001],ou[200001];
vector<int> v[200001];
vector<ib> ask[200001],query[200001];
struct fen
{
    int bit[200001];
    void upd(int x,int y,int cost)
    {
        y++;
        for(x; x<=n; x+=x&-x)
            bit[x]+=cost;
        for(y; y<=n; y+=y&-y)
            bit[y]-=cost;
    }
    int get(int x)
    {
        int s=0;
        for(x; x; x-=x&-x)
            s+=bit[x];
        return s;
    }
} fen;
ib mer(ib a,ib b)
{
    if(a.a<=b.a) return a;
    return b;
}
int get(int l,int r)
{
    int k=log2(r-l+1);
    return mer(st[k][l],st[k][r-mask(k)+1]).b;
}
void build_tree(int l,int r)
{
    int mid=get(l,r);
    if(l<=mid-1)
    {
        int ax=get(l,mid-1);
        v[mid].pb(ax);
        par[0][ax]=mid;
        if(l!=mid-1)
        {
            build_tree(l,mid-1);
        }
    }
    if(r>=mid+1)
    {
        int ax=get(mid+1,r);
        v[mid].pb(ax);
        par[0][ax]=mid;
        if(mid+1!=r)
        {
            build_tree(mid+1,r);
        }
    }
}
int finc(int cost,int x)
{
    for(int i=17; i>=0; --i)
        if(a[par[i][x]]>=cost)
            x=par[i][x];
    return x;
}
void dfs(int x)
{
    in[x]=++dem;
    for(auto f:v[x])
        dfs(f);
    ou[x]=dem;
    for(auto f:v[x])
    {
        dp[x]+=dp[f];
        fen.upd(in[x]+1,ou[x],dp[f]);
        fen.upd(in[f],ou[f],-dp[f]);
    }
    for(auto f:query[x])
    {
        s2=finc(f.a,x);
        ask[s2].pb({x,dp[x]+f.b});
    }
    for(auto f:ask[x])
        dp[x]=max(dp[x],fen.get(in[f.a])+f.b);
}
void phongbeo()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i],a[i]=n-a[i],st[0][i]= {a[i],i};
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r>>s2;
        s5+=s2;
        query[l].pb({n-r+1,s2});
    }
    for(int i=1; i<18; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=mer(st[i-1][j],st[i-1][j+mask(i-1)]);
    build_tree(1,n);
    for(int i=1; i<18; i++)
        for(int j=1; j<=n; j++)
            par[i][j]=par[i-1][par[i-1][j]];
    int root=get(1,n);
    dfs(root);
    cout<<s5-dp[root];
}

Compilation message (stderr)

constellation3.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main()
      | ^~~~
constellation3.cpp: In function 'int main()':
constellation3.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:79:9: note: in expansion of macro 'fin'
   79 |         fin(task2);
      |         ^~~
constellation3.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
constellation3.cpp:80:9: note: in expansion of macro 'fou'
   80 |         fou(task2);
      |         ^~~
constellation3.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:84:9: note: in expansion of macro 'fin'
   84 |         fin(task);
      |         ^~~
constellation3.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
constellation3.cpp:85:9: note: in expansion of macro 'fou'
   85 |         fou(task);
      |         ^~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65