Submission #634507

#	Time	Username	Problem	Language	Result	Execution time	Memory
634507		Cross_Ratio	Gorgeous Pill (FXCUP3_gorgeous)	C++14	0 / 100	1 ms	384 KiB

gorgeous

#include <bits/stdc++.h>
using namespace std;
int C[300005];
long long int D[300005];
long long int DP[1005][1005];
const long long int INF = 1e18;
struct SegTree {
    vector<long long int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = max(seg[2*n], seg[2*n+1]);
            n /= 2;
        }
    }
    void Edit(int n, long long int a) {
        seg[n+MAX/2] = max(seg[n+MAX/2], a);
        update(n);
    }
    long long int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return max(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
    }
};
typedef pair<long long int, long long int> P;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> C[i];
    for(i=0;i<N;i++) cin >> D[i];
    for(i=0;i<N;i++) {
        vector<vector<P>> V1, V2;
        V1.resize(N);
        V2.resize(N);
        for(j=0;j<N;j++) {
            if(i<j) {
                if(0<=j-C[j]+1&&j-C[j]+1<=i) {
                    V2[j-C[j]+1].push_back(P(j,D[j]));
                }
            }
            else if(j<i) {
                if(j+C[j]-1<N&&i<=j+C[j]-1) {
                    V1[j].push_back(P(j+C[j]-1,D[j]));
                }
            }
        }
        SegTree tree1(N+5);
        SegTree tree2(N+5);
        int MAX = tree1.MAX;
        if(C[i]==1) tree1.Edit(i, D[i]);
        for(j=i;j>=0;j--) {
            vector<array<long long int, 2>> Query;
            for(P k : V1[j]) {
                long long int val1 = tree1.sum(0, k.first + 1, 1, 0, MAX/2);
                long long int val2 = tree2.sum(0, k.first, 1, 0, MAX/2);
                Query.push_back({k.first, max(val1, val2) + k.second});
                //tree1.Edit(k.first, max(val1, val2) + k.second);
            }
            sort(V2[j].begin(),V2[j].end());
            for(P k : V2[j]) {
                long long int val1 = tree1.sum(0, k.first, 1, 0, MAX/2);
                long long int val2 = tree2.sum(0, k.first, 1, 0, MAX/2);
                tree2.Edit(k.first, max(val1, val2) + k.second);
            }
            for(auto it : Query) {
                tree1.Edit(it[0], it[1]);
            }
        }
        cout << max(tree1.sum(0, MAX/2, 1, 0, MAX/2), tree2.sum(0, MAX/2, 1, 0, MAX/2)) << ' ';
    }
}

Compilation message (stderr)

gorgeous.cpp: In member function 'long long int SegTree::sum(int, int, int, int, int)':
gorgeous.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49