oj.uz

Submission #1107546

# Submission time Handle Problem Language Result Execution time Memory
1107546 2024-11-01T12:36:11 Z Ahmed57 Mosaic (IOI24_mosaic) C++17
53 / 100
 113 ms 31676 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int arr1[3][200001];
int arr2[200001][3];
int ans[400001];
void upd(int x,int y,int val){
    if(x<3){
        arr1[x][y] = val;
    }
    if(y<3){
        arr2[x][y] = val;
    }
}
int get(int x,int y){
    if(x<3)return arr1[x][y];
    else return arr2[x][y];
}
vector<long long> mosaic(vector<int32_t> X, vector<int32_t> Y, vector<int32_t> T, vector<int32_t> B, vector<int32_t> L, vector<int32_t> R) {
    int n = X.size();
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(i>=3&&j>=3)break;
            if(i==0){
                upd(i,j,X[j]);
            }else if(j==0){
                upd(i,j,Y[i]);
            }else{
                upd(i,j,((get(i-1,j)==0&&get(i,j-1)==0)?1:0));
            }
            ans[i-j+n] = get(i,j);
        }
    }
    for(int i = 1;i<2*n;i++){
        ans[i]+=ans[i-1];
    }
    for(int i = 0;i<3;i++){
        for(int j = 1;j<n;j++){
            arr1[i][j]+=arr1[i][j-1];
            arr2[j][i]+=arr2[j-1][i];
        }
    }
    vector<int> anss;
    for(int i = 0;i<T.size();i++){
        int x1 = T[i] , x2 = B[i];
        int y1 = L[i] , y2 = R[i];
        long long all = 0;
        while(x1<=min(2ll,x2)){
            all+=arr1[x1][y2]-(y1==0?0:arr1[x1][y1-1]);
            x1++;
        }
        while(y1<=min(2ll,y2)){
            all+=arr2[x2][y1]-(x1==0?0:arr2[x1-1][y1]);
            y1++;
        }
        int mi = (x1-y2+n);
        int ma = (x2-y1+n);
        int lon = min(y2-y1+1,x2-x1+1);
        all+=(ans[ma]-ans[mi-1])*lon;
        anss.push_back(all);
    }
    return anss;
}

Compilation message

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:44:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0;i<T.size();i++){
      |                   ~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6652 KB Output is correct
8 Correct 1 ms 6480 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6652 KB Output is correct
8 Correct 1 ms 6480 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Incorrect 1 ms 8528 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 25528 KB Output is correct
2 Correct 79 ms 29436 KB Output is correct
3 Correct 107 ms 28856 KB Output is correct
4 Correct 89 ms 29372 KB Output is correct
5 Correct 86 ms 27324 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6652 KB Output is correct
8 Correct 1 ms 6480 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Incorrect 1 ms 8528 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 18108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 25544 KB Output is correct
2 Correct 109 ms 31204 KB Output is correct
3 Correct 96 ms 29628 KB Output is correct
4 Correct 89 ms 29828 KB Output is correct
5 Correct 91 ms 31676 KB Output is correct
6 Correct 87 ms 28784 KB Output is correct
7 Correct 79 ms 28064 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 25528 KB Output is correct
2 Correct 79 ms 29436 KB Output is correct
3 Correct 107 ms 28856 KB Output is correct
4 Correct 89 ms 29372 KB Output is correct
5 Correct 86 ms 27324 KB Output is correct
6 Correct 87 ms 25544 KB Output is correct
7 Correct 109 ms 31204 KB Output is correct
8 Correct 96 ms 29628 KB Output is correct
9 Correct 89 ms 29828 KB Output is correct
10 Correct 91 ms 31676 KB Output is correct
11 Correct 87 ms 28784 KB Output is correct
12 Correct 79 ms 28064 KB Output is correct
13 Correct 93 ms 31168 KB Output is correct
14 Correct 96 ms 31240 KB Output is correct
15 Correct 113 ms 31428 KB Output is correct
16 Correct 99 ms 29628 KB Output is correct
17 Correct 94 ms 30908 KB Output is correct
18 Correct 94 ms 31232 KB Output is correct
19 Correct 74 ms 28348 KB Output is correct

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6480 KB Output is correct
8 Correct 1 ms 6652 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Correct 1 ms 6480 KB Output is correct
12 Incorrect 1 ms 8528 KB Output isn't correct
13 Halted 0 ms 0 KB -