oj.uz

Submission #1108339

# Submission time Handle Problem Language Result Execution time Memory
1108339 2024-11-03T21:16:18 Z Ludissey Mosaic (IOI24_mosaic) C++17
22 / 100
 1000 ms 1755764 KB 
#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

int q,n;
vector<vector<int>> lft;
vector<vector<int>>  top; 

vector<int> dia;
// X cest le top
// Y cest la gauche

// [le x][le y]

int todia(int x, int y){
  return (n-x-1)+y;
}

std::vector<long long> mosaic(std::vector<signed> X, std::vector<signed> Y, std::vector<signed> T, std::vector<signed> B,std::vector<signed> L, std::vector<signed> R) {
  q = sz(T); n=sz(Y);
  lft.resize(2,vector<int>(n,0));
  top.resize(n,vector<int>(2,0));
  dia.resize(n+n-1,0);
  for (int i = 0; i < n; i++)
  {
    lft[0][i]=Y[i];
    top[i][0]=X[i];
  }
  if(n>1){
    lft[1][0]=X[1];
    top[0][1]=Y[1];
  }
  for (int i = 1; i < n&&n>1; i++)
  {
    top[i][1]=(top[i-1][1]==0&&top[i][0]==0);
    lft[1][i]=(lft[1][i-1]==0&&lft[0][i]==0);
    dia[todia(i,1)]=top[i][1];
    dia[todia(1,i)]=lft[1][i];

  }
  
  vector<vector<int>> fullgrid(n,vector<int>(n,0));
  vector<vector<int>> fakegrid(n,vector<int>(n,0));
  vector<vector<int>> prefix(n,vector<int>(n,0));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < min(n,2LL); j++)
    {
      fullgrid[i][j]=top[i][j];
      fullgrid[j][i]=lft[j][i];
    }
  }
  for (int i = 0; i < n; i++)
  {
    fakegrid[i][0]=X[i];
    fakegrid[0][i]=Y[i];
  }

  for (int i = 1; i < n; i++){
    for (int j = 1; j < n; j++)
    {
      fakegrid[i][j]=(fakegrid[i-1][j]==0&&fakegrid[i][j-1]==0);
    }
  }

  for (int i = 2; i < n; i++){
    for (int j = 2; j < n; j++)
    {
      fullgrid[i][j]=dia[todia(i,j)];
      fullgrid[j][i]=dia[todia(j,i)];
    }
  }
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++)
    {
      prefix[i][j]=fakegrid[i][j];
      if(i>0) prefix[i][j]+=prefix[i-1][j];
      if(j>0) prefix[i][j]+=prefix[i][j-1];
      if(i>0&&j>0) prefix[i][j]-=prefix[i-1][j-1];
      //cerr << fullgrid[j][i] << " ";
    }
    //cerr << "\n";
  }
  //cerr<<"\n";
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++)
    {
      //cerr << fakegrid[j][i] << " ";
      //if(fakegrid[j][i]!=fullgrid[j][i]) cout << "ERROR - " << i << " " << j << "\n";
    }
    //cerr << "\n";
  }
  std::vector<long long> C(q, 0);
  for (int i = 0; i < q; i++)
  {
    int l=L[i],r=R[i],t=T[i],b=B[i];
    int sm=prefix[r][b];
    if(l>0) sm-=prefix[l-1][b];
    if(t>0) sm-=prefix[r][t-1];
    if(l>0&&t>0) sm+=prefix[l-1][t-1]; 
    C[i]=sm;
  }
  return C;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 2 ms 1360 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 2 ms 1360 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 760 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1221 ms 1481020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 2 ms 1360 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 2 ms 1360 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 760 KB Output is correct
18 Correct 753 ms 599884 KB Output is correct
19 Correct 765 ms 599940 KB Output is correct
20 Correct 764 ms 599632 KB Output is correct
21 Correct 754 ms 599768 KB Output is correct
22 Correct 752 ms 599624 KB Output is correct
23 Correct 156 ms 102768 KB Output is correct
24 Correct 174 ms 103028 KB Output is correct
25 Correct 157 ms 103240 KB Output is correct

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8176 KB Output is correct
2 Execution timed out 1188 ms 1671496 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1198 ms 1755764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1221 ms 1481020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 1360 KB Output is correct
13 Correct 2 ms 1360 KB Output is correct
14 Correct 2 ms 1388 KB Output is correct
15 Correct 2 ms 1360 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 1 ms 760 KB Output is correct
19 Execution timed out 1221 ms 1481020 KB Time limit exceeded
20 Halted 0 ms 0 KB -