Submission #859342

#TimeUsernameProblemLanguageResultExecution timeMemory
859342chrispham258Triple Jump (JOI19_jumps)C++17
100 / 100
751 ms95272 KiB
/* Pham Ngoc Tho aka Chis Pham */ /* [Author : Pham Ngoc Tho] - THPT Chuyen Nguyen Du */ /* [ 2024 - 12TH GO VOI 24 ] - From Nguyen Du with love */ // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include<bits/stdc++.h> using namespace std; #define oo 0x3f #define ff first #define ss second #define endl "\n" #define ins insert #define chis id<<1 #define pham (id<<1) + 1 #define sqr(x) ((x) * 1ll * (x)) #define gcd(a, b) __gcd(a, b) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(),x.rend() #define repu(i, x, n) for(int i = x; i <= n; ++i) #define repd(i, n, x) for(int i = n; i >= x; --i) #define reset(x, val) memset(x, val, sizeof(x)) typedef double db; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll, ll> pll; template<class T> bool getbit(T val, int i) { return (val >> i) & 1; } template<class T> int cntbit(T val) { return val == 0 ? 0 : cntbit(val >> 1) + (val & 1); } template<class T> ll fpow(T a, const T b) { ll res = 1, x = a, y = b; while(y){if(y & 1)res *= x; x = x * x; y>>=1;}; return res; } template<class T> ll modfpow(T a, T b, const T &m) { ll res = 1, x = a, y = b; x %= m; while(y){if(y & 1){res *= x; res %= m;}; x = x * x; x %= m; y >>= 1; } return res % m; } template<class T> T lcm(T &a, T &b) { return a / gcd(a, b) * b; } const int mod = 1e9 + 7; const int INF = 1e9 + 7; const ll LNF = 1e18 + 7; inline char gc() { static char buf[1 << 23]; static size_t bc, be; if(bc >= be){ buf[0] = 0, bc = 0; be = fread(buf, 1, sizeof(buf), stdin); } return buf[bc++]; } ll readLL() { ll a, c; while ((a = gc()) < 20); if (a == '-') return -readLL(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; } int readInt() { int a, c; while ((a = gc()) < 10); if (a == '-') return -readInt(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; } mt19937 RND(time(nullptr)); ll rnd(ll l, ll r) { assert(l <= r);ll L = l, R = r; ll aft = (L + RND() * 1LL % (R - L + 1)); return aft; } #define TASK "name" #define FILE "DEBUG" void setIO() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);} if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);} } template<class T> T multi(const T &a, const T &b) { T res = (a*b)%mod; return res;} template<class T> bool umax(T &a, T b) { if(a < b){ a = b; return 1;} else return 0;} template<class T> bool umin(T &a, T b) { if(a > b){ a = b; return 1;} else return 0;} const int NmX = 5e5 + 7; const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; int n; ll a[NmX]; void read() { cin >> n; repu(i, 1, n) cin >> a[i]; } namespace sub2{ const int N = 5e3 + 7; class IT{ public: int it[4 * N]; void build(int id, int l, int r){ if(l == r){ it[id] = a[l]; return; } int mid = (l + r) >> 1; build(chis, l, mid); build(pham, mid + 1, r); it[id] = max(it[chis], it[pham]); } int get(int id, int l, int r, int u, int v){ if(r < u || v < l) return -INF; if(u <= l && r <= v) return it[id]; int mid = (l + r) >> 1; return max(get(chis, l, mid, u, v), get(pham, mid + 1, r, u, v)); } }IT; ll f[N][N], fi[N][N]; void solve(){ IT.build(1, 1, n); repu(i, 1, n) { repu(j, i + 2, n) { int k = (i + j)/2; f[i][j] = a[i] + a[j] + IT.get(1, 1, n, i + 1, k); umax(f[i][j], f[i][j - 1]); } } repd(i, n, 1){ repu(j, 1, n) umax(f[i - 1][j], f[i][j]); } int q; cin >> q; while(q--){ int u, v; cin >> u >> v; cout << f[u][v] << endl; } } } namespace sub3{ const int N = 2e5 + 7; ll pre[2 * N]; void solve(){ stack<int> st; repu(i, 1, n){ while(st.size() && a[st.top()] < a[i]){ umax(pre[2 * i - st.top()], a[i] + a[st.top()]); st.pop(); } if(st.size()) umax(pre[2 * i - st.top()], a[i] + a[st.top()]); st.push(i); } repu(i, 1, n) umax(pre[i], pre[i - 1]); ll res = 0; repu(i, 1, n) umax(res, pre[i] + a[i]); cout << res; } } namespace sub4{ vector<pii> qr[NmX], upd[NmX]; int res[NmX]; struct node{ int pre, val, sum; node(){ pre = val = sum = 0; }; node(int pre, int val, int sum) : pre(pre), val(val), sum(sum) {}; friend node operator + (const node &x, const node &y){ return node(max(x.pre, y.pre), max(x.val, y.val), max({x.sum, y.sum, x.pre + y.val})); } }; node it[4 * NmX]; void build(int id, int l, int r){ if(l == r){ it[id] = node(0, a[l], a[l]); return; } int mid = (l + r) >> 1; build(chis, l, mid); build(pham, mid + 1, r); it[id] = it[chis] + it[pham]; } void update(int id, int l, int r, int pos, int val){ if(r < pos || pos < l) return; if(l == r && r == pos){ umax(it[id].pre, val); it[id].sum = it[id].pre + it[id].val; return; } int mid = (l + r) >> 1; update(chis, l, mid, pos, val); update(pham, mid + 1, r, pos, val); it[id] = it[chis] + it[pham]; } node query(int id, int l, int r, int u, int v){ if(r < u || v < l) return node(0, 0, 0); if(u <= l && r <= v) return it[id]; int mid = (l + r) >> 1; return query(chis, l, mid, u, v) + query(pham, mid + 1, r, u, v); } void solve(){ int q; cin >> q; repu(i, 1, q){ int l, r; cin >> l >> r; qr[l].eb(pii(r, i)); } build(1, 1, n); stack<int> st; repu(i, 1, n){ while(st.size() && a[st.top()] < a[i]){ int j = st.top(); upd[j].eb(pii(i, a[i] + a[j])); st.pop(); } if(st.size()) upd[st.top()].eb(pii(i, a[i] + a[st.top()])); st.push(i); } repd(i, n, 1){ for(pii x : upd[i]) if(2 * x.ff - i <= n) update(1, 1, n, 2 * x.ff - i, x.ss); for(pii x : qr[i]) res[x.ss] = query(1, 1, n, i, x.ff).sum; } repu(i, 1, q) cout << res[i] << endl; } } void process() { // if(n <= 5000) sub2::solve(); // else sub3::solve(); sub4::solve(); } main() { setIO(); int test = 1; // cin >> test; while(test--) { read(); process(); } cerr << "Time elapsed: " << (1.0 * clock()/CLOCKS_PER_SEC) * 1000 << "ms.\n"; return 0; }

Compilation message (stderr)

jumps.cpp:250:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  250 | main()
      | ^~~~
jumps.cpp: In function 'void setIO()':
jumps.cpp:62:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:62:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:63:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:63:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...