Submission #634546

#	Time	Username	Problem	Language	Result	Execution time	Memory
634546		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 {
    struct Node {
        long long int ma, p;
        Node() : ma(0), p(0) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].p) {
            seg[n].ma += seg[n].p;
            if(n<MAX/2) {
                seg[2*n].p += seg[n].p;
                seg[2*n+1].p += seg[n].p;
            }
            seg[n].p = 0;
        }
    }
    void add(int s, int e, long long int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].p += k;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s,e,k,2*n,ns,mid);
        add(s,e,k,2*n+1,mid,ne);
        if(n<MAX/2) seg[n].ma = max(seg[2*n].ma, seg[2*n+1].ma);
    }
    long long int sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n].ma;
        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;
vector<long long int> Naive(int N) {
    int i, j;
    vector<long long int> ans;
    for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            for(int k = 0; k <= N; k++) DP[j][k] = -INF;
        }
        DP[i][i+1] = (C[i]==1 ? D[i] : 0);
        for(int len = 1; len < N; len++) {
            for(j=0;j+len<=N;j++) {
                if(j+len+1<=N) {
                    DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
                }
                if(j >= 1) {
                    DP[j-1][j+len] = max(DP[j-1][j+len], DP[j][j+len] + (C[j-1] == len + 1 ? D[j-1] : 0));
                }
            }
        }
        ans.push_back(DP[0][N]);
    }
    return ans;
}
vector<vector<int>> adj;
int s[600005];
int e[600005];
int cnt = 0;
void dfs(int c) {
    s[c] = cnt;
    for(int n : adj[c]) dfs(n);
    if(adj[c].size()==0) cnt++;
    e[c] = cnt;
}
vector<long long int> NlogN_Solution(int N) {
    int i, j;
    vector<vector<array<long long int, 3>>> V1, V2;
    V1.resize(N);
    V2.resize(N);
    vector<array<int, 3>> Node;
    for(j=0;j<N;j++) {
        if(C[j]!=1 && 0<=j-C[j]+1) {
            Node.push_back({j-C[j]+1, j, 1});
            V2[j-C[j]+1].push_back({j, D[j], Node.size() - 1});
        }
        if(j+C[j]-1<N) {
            Node.push_back({j, j+C[j]-1, 0});
            V1[j].push_back({j+C[j]-1, D[j], Node.size()-1});
        }
    }
    adj.resize(Node.size());
    set<P> tree1, tree2;
    for(j=N-1;j>=0;j--) {
        for(auto k : V1[j]) {
            auto it1 = tree1.begin();
            while(it1 != tree1.end()) {
                if(it1->first >= k[0] + 1) break;
                adj[k[2]].push_back(it1->second);
                auto it2 = it1;
                it1++;
                tree1.erase(it2);
            }
            auto it2 = tree2.begin();
            while(it2 != tree2.end()) {
                if(it2->first >= k[0]+1) break;
                adj[k[2]].push_back(it2->second);
                auto it3 = it2;
                it2++;
                tree2.erase(it3);
            }
            tree1.insert(P(k[0], k[2]));
        }
        for(auto k : V2[j]) {
            auto it1 = tree1.begin();
            while(it1 != tree1.end()) {
                if(it1->first >= k[0]) break;
                adj[k[2]].push_back(it1->second);
                auto it2 = it1;
                it1++;
                tree1.erase(it2);
            }
            auto it2 = tree2.begin();
            while(it2 != tree2.end()) {
                if(it2->first >= k[0]) break;
                adj[k[2]].push_back(it2->second);
                auto it3 = it2;
                it2++;
                tree2.erase(it3);
            }
            //tree2.Edit(k.first, max(val1, val2) + k.second);
            tree2.insert(P(k[0], k[2]));
        }
    }
    for(auto it : tree1) dfs(it.second);
    for(auto it : tree2) dfs(it.second);
    //cout << "Dfs Ordered\n";
    SegTree tree(Node.size() + 5);
    int MAX = tree.MAX;
    vector<vector<array<long long int, 3>>> Qin, Qout;
    Qin.resize(N);
    Qout.resize(N);
    for(i=0;i<N;i++) {
        for(auto it : V1[i]) {
            if(i==it[0]) continue;
            if(i+1<N) Qin[i+1].push_back({s[it[2]], e[it[2]], +it[1]});
            Qout[it[0]].push_back({s[it[2]], e[it[2]], -it[1]});
        }
        for(auto it : V2[i]) {
            Qin[i].push_back({s[it[2]], e[it[2]], +it[1]});
            if(it[0]-1>=0) Qout[it[0]-1].push_back({s[it[2]], e[it[2]], -it[1]});
        }
    }
    vector<long long int> ans;
    for(i=0;i<N;i++) {
        //cout << i << "th Turn\n";
        for(auto it : Qin[i]) {
            //cout <<"Plus : " << it[0] << ' ' << it[1] << ' ' <<it[2] << '\n';
            tree.add(it[0], it[1], it[2], 1, 0, MAX/2);
        }
        long long int val = tree.sum(0, MAX/2, 1, 0, MAX/2) + (C[i]==1 ? D[i] : 0);
        ans.push_back(val);
        //cout << val << '\n';
        for(auto it : Qout[i]) {
            //cout << "Minus : " << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
            tree.add(it[0], it[1], it[2], 1, 0, MAX/2);
        }
    }
    return ans;
}
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++) {
        C[i] = rand() % (N/4) + 1;
    }
    for(i=0;i<N;i++) D[i] = rand() + 1;*/
    vector<long long int> ans1 = NlogN_Solution(N);
    //vector<long long int> ans2 = Naive(N);
    for(i=0;i<N;i++) cout << ans1[i] << ' ';
    /*for(i=0;i<N;i++) {
        if(ans1[i]!=ans2[i]) {
            cout << "Wrong Point\n";
            for(i=0;i<N;i++) cout << C[i] << ' ';
            cout << '\n';
            for(i=0;i<N;i++) cout << D[i] << ' ';
            cout << '\n';
            for(i=0;i<N;i++) cout << ans1[i] << ' ';
            cout << '\n';
            for(i=0;i<N;i++) cout << ans2[i] << ' ';
            cout << '\n';
            return 0;
        }
    }*/
}

Compilation message (stderr)

gorgeous.cpp: In member function 'void SegTree::add(int, int, long long int, int, int, int)':
gorgeous.cpp:38:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
gorgeous.cpp: In member function 'long long int SegTree::sum(int, int, int, int, int)':
gorgeous.cpp:47:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
gorgeous.cpp: In function 'std::vector<long long int> NlogN_Solution(int)':
gorgeous.cpp:93:58: warning: narrowing conversion of '(Node.std::vector<std::array<int, 3> >::size() - 1)' from 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   93 |             V2[j-C[j]+1].push_back({j, D[j], Node.size() - 1});
      |                                              ~~~~~~~~~~~~^~~
gorgeous.cpp:97:57: warning: narrowing conversion of '(Node.std::vector<std::array<int, 3> >::size() - 1)' from 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   97 |             V1[j].push_back({j+C[j]-1, D[j], Node.size()-1});
      |                                              ~~~~~~~~~~~^~
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:185:12: warning: unused variable 'j' [-Wunused-variable]
  185 |     int i, j;
      |            ^

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