Submission #1065717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065717		TsotneSV	Art Exhibition (JOI18_art)	C++17	0 / 100	4 ms	31580 KiB

art

#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces

// #define int long long
#define fi first
#define se second
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAXN=5e5+5; 

int n;
ll T[4*MAXN],lazy[4*MAXN];

void push(int v) {
    if(!lazy[v]) return;
    T[2*v] += lazy[v];
    lazy[2*v] += lazy[v];
    T[2*v+1] += lazy[v];
    lazy[2*v+1] += lazy[v];
    lazy[v] = 0;
}

ll query(int v,int l,int r,int tl,int tr) {
    if(l > r) return 0;
    if(l == tl and r == tr) return T[v];
    push(v);
    int tm = (tl + tr)/2;
    return max(query(2*v,l,min(r,tm),tl,tm),query(2*v+1,max(l,tm+1),r,tm+1,tr));
}

void update(int v,int l,int r,int tl,int tr,int addend) {
    if(l > r) return;
    if(l == tl and r == tr) {
        T[v] += addend;
        lazy[v] += addend;
    }else {
        push(v);
        int tm = (tl + tr)/2;
        update(2*v,l,min(r,tm),tl,tm,addend);
        update(2*v+1,max(l,tm+1),r,tm+1,tr,addend);
        T[v] = max(T[2*v],T[2*v+1]);
    }
}

signed main(){
  
    send help
    
    cin>>n; pll A[n]; memset(T,0,sizeof(T)); memset(lazy,0,sizeof(lazy));

    for(int i=0;i<n;i++) cin>>A[i].fi>>A[i].se;

    sort(A,A+n); ll ans = 0;

    for(int i=0;i<n;i++) {
        update(1,i,i,0,n-1,A[i].fi);
        update(1,0,i,0,n-1,A[i].se);
        ans = max(ans,query(1,0,i,0,n-1) - A[i].fi);
    } printl(ans);
}

Compilation message (stderr)

art.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      |

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50