Submission #853284

#	Time	Username	Problem	Language	Result	Execution time	Memory
853284		resting	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	4369 ms	1477204 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
//#include "soccer.h"

#define int long long

struct segtree{ //range max
    int l, r; 
    int v = -1;
    segtree *lc = 0, *rc = 0;
    segtree*getmem();
    segtree(int l, int r): l(l), r(r){
        if(l == r) return;
        int m = (l+r)/2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m+1, r);
    }
    segtree():segtree(-1, -1){};
    int q(int ql, int qr){
        if(ql <= l && r <= qr) return v;
        if(qr < l || ql > r) return -1;
        return max(lc->q(ql, qr), rc->q(ql, qr));
    }
    void upd(int qi, int qv){
        if(qi < l || qi > r) return;
        if(l == r){v = qv; return;}
        lc->upd(qi, qv); rc->upd(qi, qv);
        v = max(lc->v, rc->v);
    }
}mem[1024*1024*4*2]; int memsz = 0;
segtree* segtree::getmem(){return &mem[memsz++];}

int solve(int n, vector<vector<pair<int,int>>> &adj){
    vector<int> cnt(n);
    for(auto j : adj) for(auto &x : j)cnt[x.first]++;
    vector<int> q; // topological sorting
    for(int i = 0; i < n; i++) if(cnt[i] == 0) q.push_back(i);
    vector<int> sort;
    while(q.size()){
        int v = q.back();
        q.pop_back();
        sort.push_back(v);
        for(auto &x : adj[v]){
            cnt[x.first]--;
            if(cnt[x.first]==0)
            q.push_back(x.first);
        }
    }
    //sorted
    vector<int> dp(n, 0);
    int res = 0;
    for(auto &x : sort){
        res = max(res, dp[x]);
        for(auto &j : adj[x]){
            dp[j.first] = max(dp[j.first], dp[x] + j.second);
        }
    }
    return res;
}

int32_t biggest_stadium(int32_t N, std::vector<std::vector<int32_t>> F){
    map<vector<int>, int> owo; int cur = 1; 

    vector<vector<pair<int,int>>> adj(N*N+5); // shouldnt be moree??
    //set up segtree???
    vector<vector<int>> lo, hi, l;
    lo = hi = l = vector<vector<int>>(N, vector<int>(N, -1));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(j) l[i][j] = l[i][j-1];
            if(F[i][j]) l[i][j] = j;
        }
    }

    segtree uwu(0, N-1);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(F[i][j]) uwu.upd(j, i);
        }
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            lo[i][j] = uwu.q(l[i][j]+1, j)+1;
        }
    }

    uwu = segtree(0, N-1);
    for(int i = N-1; i >= 0; i--){
        for(int j = 0; j < N; j++){
            if(F[i][j]) uwu.upd(j, N-i-1);
        }
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            hi[i][j] = N-uwu.q(l[i][j]+1, j)-2;
        }
    }

    vector<vector<int>> owo2(N, vector<int>(N));

    auto extend = [&](int i, int j, int i2, int j2){
        int lo2 = lo[i][j], hi2 = hi[i][j], lo3 = lo[i2][j2], hi3 = hi[i2][j2];
        int id = owo2[i][j], id2 = owo2[i2][j2];
        adj[id].push_back(make_pair(id2, (lo2-lo3 + hi3-hi2) * (j2 - l[i2][j2])));

    };
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            int lo2 = lo[i][j];
            int hi2 = hi[i][j];
            if(!owo.count({lo2, hi2, j})) owo[{lo2, hi2, j}] = cur++;
            owo2[i][j] = owo[{lo2, hi2, j}];
        }
    }
    for(int i =  0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            int lo2 = lo[i][j];
            int hi2 = hi[i][j];
            int id = owo2[i][j];
            adj[0].push_back(make_pair(id, (hi2-lo2+1) * (j - (l[i][j]+1) + 1)));

            if(l[i][j]+1 != j){
                extend(i, j, i, j-1);
            }

            if(lo2 && !F[lo2-1][j]){
                extend(i, j, lo2-1, j);
            }

            if(hi2 < N-1 && !F[hi2+1][j]){
                extend(i, j, hi2+1, j);
            }
        }
    }
    return solve(adj.size(), adj);
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 30 / 30