Submission #1184109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184109		Swan	Catfish Farm (IOI22_fish)	C++20	100 / 100	299 ms	49248 KiB

fish

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
 
using namespace std;

const int maxn = 3e5 + 123;

struct st {
    int y = 0;
    long long val = 0;
    long long pointsBelow = 0;

    st() {}
    st (int y, long long val, long long pointsBelow) : y(y), val(val), pointsBelow(pointsBelow) {}

    bool operator< (const st& ot) const {
        return y < ot.y;
    }

    bool operator< (const int val) const {
        return y < val;
    }

    friend bool operator<(const int& val, const st& ot) {
        return val < ot.y;
    }
};

vector<st> points[maxn];
vector<long long> prefSum[maxn];

long long getSum(int col, int y) {
    if (col < 0) return 0;

    long long ans = 0;

    int num = upper_bound(points[col].begin(), points[col].end(), y) - points[col].begin();


    if (num == points[col].size()) num--;

    while (num > -1 && points[col][num].y > y) num--;

    if (num == -1) {
        return 0;
    }

    return prefSum[col][num];
}

long long solve(vector<st>& prevRise, vector<st>& prevDown, vector<st>& prevNoPiles, vector<st>& curRise, vector<st>& curDown, vector<st>& curNoPiles, vector<int>& interestingPoints, int curx) {
    
    int prevDownPointer = -1;
    int prevRisePointer = -1;
    int prevNoPilesPointer = -1;

    long long bestDown = 0;
    long long bestRise = 0;
    long long bestNoPiles = 0;
    long long bestNoPilesHigher = 0;
    long long overallMax = 0;

    for (auto a : prevNoPiles) bestNoPilesHigher = max(bestNoPilesHigher, a.val);
    
    for (int i = 0; i < interestingPoints.size(); i++) {
        while (prevRisePointer + 1 < prevRise.size() && prevRise[prevRisePointer + 1].y < interestingPoints[i]) {
            prevRisePointer++;
            bestDown = max(bestDown, prevRise[prevRisePointer].val - prevRise[prevRisePointer].pointsBelow);
        }

        while (prevNoPilesPointer + 1 < prevNoPiles.size() && prevNoPiles[prevNoPilesPointer + 1].y <= interestingPoints[i]) {
            prevNoPilesPointer++;
            bestNoPiles = max(bestNoPiles, prevNoPiles[prevNoPilesPointer].val - prevNoPiles[prevNoPilesPointer].pointsBelow);
        }

        long long numberOfPoints = 0;
        long long numberOfPointsNow = 0;

        if (curx) {
            numberOfPoints = getSum(curx - 1, interestingPoints[i]);
        }

        numberOfPointsNow = getSum(curx, interestingPoints[i]);

        long long ans = bestNoPilesHigher;
        ans = max(ans, numberOfPoints + max(bestDown, bestNoPiles));

        curRise.push_back({interestingPoints[i], ans , numberOfPointsNow});
    }

    prevDownPointer = prevDown.size();
    prevRisePointer = prevRise.size();
    bestDown = 0;
    bestRise = 0;
    bestNoPiles = 0;

    // << interestingPoints.size() << endl;

    for (int i = interestingPoints.size() - 1; i >= 0; i--) {
        while (prevRisePointer - 1 >= 0 && prevRise[prevRisePointer - 1].y >= interestingPoints[i]) {
            prevRisePointer--;
            long long numberOfPointsNowSum = getSum(curx, prevRise[prevRisePointer].y);
                        
            bestRise = max(bestRise, prevRise[prevRisePointer].val + numberOfPointsNowSum);
            bestNoPiles = max(bestNoPiles, prevRise[prevRisePointer].val);
        
            //if (curx == 4) cout << bestRise << endl;
        }

        while (prevDownPointer - 1 >= 0 && prevDown[prevDownPointer - 1].y >= interestingPoints[i]) {
            prevDownPointer--;
            long long numberOfPointsNowSum = getSum(curx, prevDown[prevDownPointer].y);

            bestDown = max(bestDown, prevDown[prevDownPointer].val + numberOfPointsNowSum);
            bestNoPiles = max(bestNoPiles, prevDown[prevDownPointer].val);
        }

        long long numberOfPointsNow = getSum(curx, interestingPoints[i]);

        long long ans = max(bestDown, bestRise) - numberOfPointsNow;
        ans = max(ans, 0ll);

        curDown.push_back({interestingPoints[i], ans , numberOfPointsNow});

        if (prevDownPointer == prevDown.size() && prevRisePointer == prevRise.size()) ans = 0;
        else ans = bestNoPiles + numberOfPointsNow;

        curNoPiles.push_back({interestingPoints[i], ans, numberOfPointsNow});
    }

    reverse(curDown.begin(), curDown.end());

    for (auto a : prevDown) overallMax = max(overallMax, a.val);
    for (auto a : prevRise) overallMax = max(overallMax, a.val);
    for (auto a : prevNoPiles) overallMax = max(overallMax, a.val);


    //cout << "OVERALL " << curx << ' ' << curNoPiles[0].val << endl;

    curNoPiles.push_back({-1, overallMax, 0});


    reverse(curNoPiles.begin(), curNoPiles.end());


    return overallMax;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {

    for (int i = 0; i < M; i++) {
        points[X[i]].push_back(st({Y[i], W[i], 0}));
    }

    for (int i = 0; i < N; i++) {
        sort(points[i].begin(), points[i].end());

        for (int j = 0; j < points[i].size(); j++) {
            points[i][j].pointsBelow = j;
            prefSum[i].push_back(points[i][j].val);
            if (j) prefSum[i][j] += prefSum[i][j - 1];
        }
    }

    vector<st> prevRise;
    vector<st> prevDown;
    vector<st> prevNoPiles;

    vector<st> curRise;
    vector<st> curDown;
    vector<st> curNoPiles;

    long long ans = 0;

    curNoPiles.push_back({-1, 0, 0});

    for (int i = 0; i < N; i++) {

        swap(prevRise, curRise);
        swap(prevDown, curDown);
        swap(prevNoPiles, curNoPiles);

        curRise.clear(); 
        curDown.clear();
        curNoPiles.clear();

        vector<int> interestingPointsUnsorted;
        vector<int> interestingPoints;

        if (i) {
            for (auto a : points[i - 1]) interestingPointsUnsorted.push_back(a.y);
        }

        for (auto a : points[i]) interestingPointsUnsorted.push_back(a.y);

        if (i + 1 < N) {
            for (auto a : points[i + 1]) interestingPointsUnsorted.push_back(a.y);
        }

        sort(interestingPointsUnsorted.begin(), interestingPointsUnsorted.end());

        for (int i = 0; i < interestingPointsUnsorted.size(); i++) {
            if (i == interestingPointsUnsorted.size() - 1) {
                interestingPoints.push_back(interestingPointsUnsorted[i]);
                continue;
            }
            
            if (interestingPointsUnsorted[i] != interestingPointsUnsorted[i + 1]) {
                interestingPoints.push_back(interestingPointsUnsorted[i]);
            }
        }
        
        ans = max(ans, solve(prevRise, prevDown, prevNoPiles, curRise, curDown, curNoPiles, interestingPoints, i));

    }

    for (auto a : curDown) {
        ans = max(ans, a.val);
    }
    for (auto a : curRise) {
        ans = max(ans, a.val);
    }
    for (auto a : curNoPiles) {
        ans = max(ans, a.val);
    }

    return ans;

}


/*
void solve() {

    int n, m; cin >> n >> m;

	vector<int> X, Y, W;

	for (int i = 0; i < m; i++) {
		int x, y, w; cin >> x >> y >> w;
		X.push_back(x);
		Y.push_back(y);
		W.push_back(w);
	}

	cout << max_weights(n, m, X, Y, W);

    // 5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3]
    //cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << endl;
    //cout << max_weights(10000, 1, {0}, {0}, {10082010}) << endl;
   // cout << max_weights(4, 3, {2, 0, 1}, {2, 0, 1}, {1, 1, 1});
    //cout << max_weights(8, 7, {5, 4, 6, 3, 0, 2, 1}, {5, 4, 6, 3, 0, 2, 1}, {1, 1, 1, 1, 1, 1, 1});
    
    
   // cout << max_weights(5, 3, {1, 2, 3}, {0,0, 0}, {1, 1, 1});

   //cout << max_weights(7, 7, {0, 1, 2, 3, 4, 5, 6}, {0, 0, 0, 0, 0, 0, 0}, {1, 2, 3, 4, 5, 6, 7});
}

int main() {
    ios_base::sync_with_stdio(0);

    solve();
}

*/

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16