Submission #1074477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074477		anango	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	643 ms	87120 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<vector<int>> pref;
vector<vector<signed>> field;

int INF = 1LL<<30;

int query(int a, int b, int c, int d) {
    if (a<c) swap(a,c);
    if (b<d) swap(b,d);
    return pref[c+1][d+1]-pref[a][d+1]-pref[c+1][b]+pref[a][b];
}

int union_length(vector<int> i1, vector<int> i2) {
    return max(i2[1],i1[1])-min(i2[0],i1[0])+1;
}

int length(vector<int> interval) {
    return interval[1]-interval[0]+1;
}

bool check(vector<int> i1, vector<int> i2) {
    //check whether the length of the union of the intervals is equal to the maximum length of the 2 
    return max(length(i1),length(i2))==union_length(i1,i2);
}

signed biggest_stadium(signed N, vector<vector<signed>> F) {
    //the stadium is valid iff for every pair of cells (a,b) and (c,d), 
    //everything in the paths (a,b) to (a,d) to (c,d) is inside
    //or everything in the paths (a,b) to (a,c) to (c,d) is inside
    n=N;
    field=F;
    pref=vector<vector<int>>(n+1,vector<int>(n+1,0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            pref[i+1][j+1] = pref[i+1][j]+pref[i][j+1]-pref[i][j]+F[i][j];
        }
    }
    vector<vector<int>> rows(n,{INF,-INF});
    vector<vector<int>> cols(n,{INF,-INF});
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (F[i][j]==0) {
                rows[i][0] = min(rows[i][0],j);
                rows[i][1] = max(rows[i][1],j);
                cols[j][0] = min(cols[j][0],i);
                cols[j][1] = max(cols[j][1],i);
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (F[i][j]==1) {
                if (rows[i][0]<=j && j<=rows[i][1]) {
                    return 0;
                }
                if (cols[j][0]<=i && i<=cols[j][1]) {
                    return 0;
                }
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (!check(rows[i],rows[j])) {
                return 0;
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (!check(cols[i],cols[j])) {
                return 0;
            }
        }
    }

    return n*n-pref[n][n];
}

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