oj.uz

Submission #1107547

# Submission time Handle Problem Language Result Execution time Memory
1107547 2024-11-01T12:41:50 Z Ahmed57 Mosaic (IOI24_mosaic) C++17
53 / 100
 118 ms 31828 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int arr1[3][200001];
int arr2[200001][3];
int ans[400001];
long long pref[400001];
long long suf[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 = 0;i<2*n;i++){
        pref[i] = ans[i]*i;
        suf[i] = ans[i]*(2*n-i);
    }
    for(int i = 1;i<2*n;i++){
        ans[i]+=ans[i-1];
        pref[i]+=pref[i-1];
        suf[i]+=suf[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-lon+1]-ans[mi+lon-2])*lon;
        if(lon>1){
            all+=(pref[mi+lon-2]-pref[mi-1])+(ans[mi+lon-2]-ans[mi-1])*((lon-1)-(mi+lon-2));
            all+=(suf[ma]-suf[ma-lon+1])+(ans[mi+lon-2]-ans[mi-1])*((1)-(2*n-ma));
        }
        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:52:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0;i<T.size();i++){
      |                   ~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 1 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 2 ms 10576 KB Output is correct
8 Correct 2 ms 10576 KB Output is correct
9 Correct 2 ms 10576 KB Output is correct
10 Correct 2 ms 10576 KB Output is correct
11 Incorrect 2 ms 12624 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 91 ms 31688 KB Output is correct
2 Correct 118 ms 31676 KB Output is correct
3 Correct 85 ms 31788 KB Output is correct
4 Correct 86 ms 31688 KB Output is correct
5 Correct 75 ms 30140 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 1 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 2 ms 10576 KB Output is correct
8 Correct 2 ms 10576 KB Output is correct
9 Correct 2 ms 10576 KB Output is correct
10 Correct 2 ms 10576 KB Output is correct
11 Incorrect 2 ms 12624 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 60 ms 22204 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 97 ms 31820 KB Output is correct
2 Correct 103 ms 31636 KB Output is correct
3 Correct 102 ms 31676 KB Output is correct
4 Correct 100 ms 31640 KB Output is correct
5 Correct 90 ms 31684 KB Output is correct
6 Correct 78 ms 29884 KB Output is correct
7 Correct 69 ms 29372 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 31688 KB Output is correct
2 Correct 118 ms 31676 KB Output is correct
3 Correct 85 ms 31788 KB Output is correct
4 Correct 86 ms 31688 KB Output is correct
5 Correct 75 ms 30140 KB Output is correct
6 Correct 97 ms 31820 KB Output is correct
7 Correct 103 ms 31636 KB Output is correct
8 Correct 102 ms 31676 KB Output is correct
9 Correct 100 ms 31640 KB Output is correct
10 Correct 90 ms 31684 KB Output is correct
11 Correct 78 ms 29884 KB Output is correct
12 Correct 69 ms 29372 KB Output is correct
13 Correct 92 ms 31676 KB Output is correct
14 Correct 104 ms 31636 KB Output is correct
15 Correct 88 ms 31632 KB Output is correct
16 Correct 100 ms 31676 KB Output is correct
17 Correct 101 ms 31816 KB Output is correct
18 Correct 87 ms 31828 KB Output is correct
19 Correct 71 ms 29648 KB Output is correct

Subtask #8
0.0 / 22.0

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