Submission #1006851

#TimeUsernameProblemLanguageResultExecution timeMemory
1006851christinelynnBigger segments (IZhO19_segments)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define pp pop_back #define mp make_pair #define fi first #define se second #define lb lower_bound #define ub upper_bound #define pll pair<ll,ll> #define pii pair<int,int> #define vl vector<ll> #define nikah ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); const ll maxn = 5e5+7, modn1 = 1e9+7, modn2 = 998244353; using namespace std; // kalo kamu ngga emas nanti nadya merasa bersalah, ayo san demi nadya!!! // Kalo emang soalnya susah, pindah soal dulu // Jangan sampe diem, pikirin sesuatu, pasti bisa!!! // Cobain semua approach, jangan ngestuck di satu pemikiran // Jangan overthinking, jangan panik, tenangin pikiranmu ll t,n; ll pref[maxn],pos[maxn],dp[maxn]; void solve() { cin>>n; for (ll i=1; i<=n; i++) { ll x; cin>>x; pref[i] = x + pref[i-1]; } ll cur = 0; for (ll i=1; i<=n; i++) { while (cur <= n && i <= n && pref[i] - pref[cur] >= pref[cur] - pref[pos[cur]]) { cur++; } cur--; pos[i] = cur; dp[i] = dp[pos[i]] + 1; } for (ll i=1; i<=n; i++) { cout<<dp[i]<<" "; } cout<<endl; for (ll i=1; i<=n; i++) { cout<<pos[i]<<" "; } // cout<<dp[n]<<endl; } int main () { nikah t = 1; // cin>>t; while (t--) { solve(); // cout<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...