oj.uz

Submission #1108798

# Submission time Handle Problem Language Result Execution time Memory
1108798 2024-11-05T06:25:52 Z KasymK Mosaic (IOI24_mosaic) C++17
22 / 100
 292 ms 307400 KB 
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 5005;
int v[N][N];
ll p[N][N], par[N];

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
    memset(v, -1, sizeof v);
    int n = (int)X.size();
    if(n >= N){
        for(int i = 1; i <= n; ++i)
            par[i] = par[i-1]+X[i-1];
        int Q = (int)T.size();
        vector<ll> ans;
        for(int i = 0; i < Q; ++i)
            ans.pb(R[i]+1-L[i]);
        return ans;
    }
    for(int i = 1; i <= n; ++i)
        par[i] = par[i-1]+X[i-1], v[1][i] = X[i-1];
    for(int i = 1; i <= n; ++i)
        v[i][1] = Y[i-1];
    auto wow = [&](int a, int b) -> int {
        return (!(a|b)?1:0);
    };
    auto sm = [&](int x, int x1, int y, int y1) -> ll {
        return (p[x1][y1]+p[x-1][y-1]-p[x-1][y1]-p[x1][y-1]);
    };
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(v[i][j]==-1 and ~v[i-1][j] and ~v[i][j-1])
                v[i][j] = wow(v[i-1][j], v[i][j-1]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i][j];
    int Q = (int)L.size();
    vector<ll> ans;
    for(int i = 0; i < Q; ++i)
        ans.pb(sm(T[i]+1, B[i]+1, L[i]+1, R[i]+1));
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 99572 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 99408 KB Output is correct
2 Correct 12 ms 99344 KB Output is correct
3 Correct 13 ms 99412 KB Output is correct
4 Correct 13 ms 99292 KB Output is correct
5 Correct 13 ms 99408 KB Output is correct
6 Correct 13 ms 99408 KB Output is correct
7 Correct 14 ms 99408 KB Output is correct
8 Correct 12 ms 99348 KB Output is correct
9 Correct 13 ms 99580 KB Output is correct
10 Correct 12 ms 99408 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 99408 KB Output is correct
2 Correct 12 ms 99344 KB Output is correct
3 Correct 13 ms 99412 KB Output is correct
4 Correct 13 ms 99292 KB Output is correct
5 Correct 13 ms 99408 KB Output is correct
6 Correct 13 ms 99408 KB Output is correct
7 Correct 14 ms 99408 KB Output is correct
8 Correct 12 ms 99348 KB Output is correct
9 Correct 13 ms 99580 KB Output is correct
10 Correct 12 ms 99408 KB Output is correct
11 Correct 14 ms 100408 KB Output is correct
12 Correct 14 ms 100432 KB Output is correct
13 Correct 14 ms 100432 KB Output is correct
14 Correct 13 ms 100432 KB Output is correct
15 Correct 13 ms 99920 KB Output is correct
16 Correct 13 ms 99920 KB Output is correct
17 Correct 13 ms 99920 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 265288 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 99408 KB Output is correct
2 Correct 12 ms 99344 KB Output is correct
3 Correct 13 ms 99412 KB Output is correct
4 Correct 13 ms 99292 KB Output is correct
5 Correct 13 ms 99408 KB Output is correct
6 Correct 13 ms 99408 KB Output is correct
7 Correct 14 ms 99408 KB Output is correct
8 Correct 12 ms 99348 KB Output is correct
9 Correct 13 ms 99580 KB Output is correct
10 Correct 12 ms 99408 KB Output is correct
11 Correct 14 ms 100408 KB Output is correct
12 Correct 14 ms 100432 KB Output is correct
13 Correct 14 ms 100432 KB Output is correct
14 Correct 13 ms 100432 KB Output is correct
15 Correct 13 ms 99920 KB Output is correct
16 Correct 13 ms 99920 KB Output is correct
17 Correct 13 ms 99920 KB Output is correct
18 Correct 253 ms 306196 KB Output is correct
19 Correct 242 ms 306628 KB Output is correct
20 Correct 218 ms 306372 KB Output is correct
21 Correct 217 ms 307400 KB Output is correct
22 Correct 203 ms 306372 KB Output is correct
23 Correct 120 ms 167612 KB Output is correct
24 Correct 107 ms 167868 KB Output is correct
25 Correct 108 ms 167872 KB Output is correct

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 110268 KB Output is correct
2 Runtime error 292 ms 267364 KB Execution killed with signal 7
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 272 ms 268104 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 265288 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 99572 KB Output is correct
2 Correct 14 ms 99408 KB Output is correct
3 Correct 12 ms 99344 KB Output is correct
4 Correct 13 ms 99412 KB Output is correct
5 Correct 13 ms 99292 KB Output is correct
6 Correct 13 ms 99408 KB Output is correct
7 Correct 13 ms 99408 KB Output is correct
8 Correct 14 ms 99408 KB Output is correct
9 Correct 12 ms 99348 KB Output is correct
10 Correct 13 ms 99580 KB Output is correct
11 Correct 12 ms 99408 KB Output is correct
12 Correct 14 ms 100408 KB Output is correct
13 Correct 14 ms 100432 KB Output is correct
14 Correct 14 ms 100432 KB Output is correct
15 Correct 13 ms 100432 KB Output is correct
16 Correct 13 ms 99920 KB Output is correct
17 Correct 13 ms 99920 KB Output is correct
18 Correct 13 ms 99920 KB Output is correct
19 Runtime error 244 ms 265288 KB Execution killed with signal 7
20 Halted 0 ms 0 KB -