Submission #254817

#	Time	Username	Problem	Language	Result	Execution time	Memory
254817		Mercenary	Feast (NOI19_feast)	C++14	100 / 100	226 ms	138232 KiB

feast

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"
#define int long long
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 3e5 + 5;
struct Node{
    int sum , pre , suf , res;
    int ppre , psuf , pl , pr;
    Node(){};
    Node(int sum , int pre , int suf , int res,int ppre , int psuf , int pl , int pr)
        :sum(sum),pre(pre),suf(suf),res(res),ppre(ppre),psuf(psuf),pl(pl),pr(pr){};
    Node operator + (const Node other){
        if(ppre == -1)return other;
        if(other.ppre == -1)return (*this);
        Node ans;
        if(res < other.res)ans = other;
        else ans = (*this);
        ans.sum = sum + other.sum;
        if(pre > sum + other.pre){
            ans.pre = pre;
            ans.ppre = ppre;
        }else{
            ans.pre = sum + other.pre;
            ans.ppre = other.ppre;
        }
        if(other.suf > other.sum + suf){
            ans.suf = other.suf;
            ans.psuf = other.psuf;
        }else{
            ans.suf = other.sum + suf;
            ans.psuf = psuf;
        }
        if(ans.res < suf + other.pre){
            ans.res = suf + other.pre;
            ans.pl = psuf;
            ans.pr = other.ppre;
        }
        return ans;
    }
}s[maxn * 4] , rs[maxn * 4];
int n , k;
bool lz[maxn * 4];
int a[maxn];
void Build(int x , int l , int r){
    if(l == r){
        s[x] = Node(a[l],a[l],a[l],a[l],l,l,l,l);
        rs[x] = Node(-a[l],-a[l],-a[l],-a[l],l,l,l,l);
        return;
    }
    int mid = l + r >> 1;
    Build(x*2,l,mid);
    Build(x*2+1,mid+1,r);
    s[x] = s[x * 2] + s[x * 2 + 1];
    rs[x] = rs[x * 2] + rs[x * 2 + 1];
}
void Push(int x , bool key){
    if(lz[x])swap(s[x],rs[x]);
    if(key){
        lz[x * 2] ^= lz[x];
        lz[x * 2 + 1] ^= lz[x];
    }
    lz[x] = 0;
}
void update(int x , int l , int r , int pos ,int val){
    Push(x,l!=r);
    if(l == r){
        a[l] = val;
        s[x] = Node(a[l],a[l],a[l],a[l],l,l,l,l);
        rs[x] = Node(-a[l],-a[l],-a[l],-a[l],l,l,l,l);
        lz[x] = 0;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid)update(x*2,l,mid,pos,val);
    else update(x*2+1,mid+1,r,pos,val);
    s[x] = s[x * 2] + s[x * 2 + 1];
    rs[x] = rs[x * 2] + rs[x * 2 + 1];
}

void Rev(int x , int l , int r , int L , int R){
    Push(x,l!=r);
    if(L > r || l > R)return;
    if(L <= l && r <= R){
        lz[x] ^= 1;
        Push(x,l!=r);
        return;
    }
    int mid = l + r >> 1;
    Rev(x*2,l,mid,L,R);Rev(x*2+1,mid+1,r,L,R);
    s[x] = s[x * 2] + s[x * 2 + 1];
    rs[x] = rs[x * 2] + rs[x * 2 + 1];
}
Node Query(int x , int l , int r , int L , int R){
    Push(x,l!=r);
    if(L > r || l > R)return Node(-1,-1,-1,-1,-1,-1,-1,-1);
    if(L <= l && r <= R)return s[x];
    int mid = l + r >> 1;
    return Query(x*2,l,mid,L,R)+Query(x*2+1,mid+1,r,L,R);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> k;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i];
    }
    Build(1,1,n);
    ll res = 0;
    while(k--){
        if(s[1].res <= 0)break;
        res += s[1].res;
        Rev(1,1,n,s[1].pl,s[1].pr);
    }
    cout << res;
}

Compilation message (stderr)

feast.cpp: In function 'void Build(long long int, long long int, long long int)':
feast.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
feast.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
feast.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
feast.cpp: In function 'void Rev(long long int, long long int, long long int, long long int, long long int)':
feast.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
feast.cpp: In function 'Node Query(long long int, long long int, long long int, long long int, long long int)':
feast.cpp:107:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
feast.cpp: In function 'int32_t main()':
feast.cpp:116:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:117:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29