제출 #1213434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213434		Ak_16	Mosaic (IOI24_mosaic)	C++20	100 / 100	97 ms	29252 KiB

mosaic

#include <iostream>
#include <vector>
#include "mosaic.h"
#define ll long long
using namespace std;

int r1[200005];
int r2[200005];
int c1[200005];
int c2[200005];
ll r1psum[400005];
ll r2psum[400005];
ll c1psum[400005];
ll c2psum[400005];
ll psum[400005];
ll spsum[400005];
int fin[400005];
int n;

ll getsm(int to, int bo, int le, int ri){
  to++;
  bo++;
  le++;
  ri++;
  ll sm = 0LL;
  
  if(to==1){
    sm += r1psum[ri] - r1psum[le-1];
    to++;
    if(bo==1){return sm;}
  }
  
  if(to==2){
    sm += r2psum[ri] - r2psum[le-1];
    to++;
    if(bo==2){return sm;}
  }
  
  if(le==1){
    sm += c1psum[bo] - c1psum[to-1];
    le++;
    if(ri==1){return sm;}
  }
  
  if(le==2){
    sm += c2psum[bo] - c2psum[to-1];
    le++;
    if(ri==2){return sm;}
  }
  
  int n1 = min(ri-le+1, bo-to+1);
  int n2 = max(ri-le+1, bo-to+1);
  
  int st = n + to - ri;
  int en = n + bo - le;
  
  sm += spsum[st+n1-2] - spsum[st-1];
  sm -= (psum[st+n1-2] - psum[st-1]) * 1LL * (st-1);
  
  sm -= (spsum[en] - spsum[en+1-n1]);
  sm += (psum[en] - psum[en+1-n1]) * 1LL * (en+1);
  
  sm += (psum[en+1-n1] - psum[st+n1-2]) * 1LL * n1;
  
  return sm;
  
  
}

vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r){
  
  n = x.size();
  
  for(int i=0; i<n; i++){
    r1[i+1] = x[i];
  }
  
  for(int i=0; i<n; i++){
    c1[i+1] = y[i];
  }
  
  r1psum[0] = 0LL;
  for(int i=1; i<=n; i++){
    r1psum[i] = r1psum[i-1] + r1[i] * 1LL;
  }
  
  c1psum[0] = 0LL;
  for(int i=1; i<=n; i++){
    c1psum[i] = c1psum[i-1] + c1[i] * 1LL;
  }
  
  if(n>1){
    r2[1] = c1[2];
    c2[1] = r1[2];
  }
  
  for(int i=2; i<=n; i++){
    r2[i] = (1-r2[i-1]) * (1-r1[i]);
    c2[i] = (1-c2[i-1]) * (1-c1[i]);
  }
  
  if(n>=2){
    r2psum[0] = 0LL;
  for(int i=1; i<=n; i++){
    r2psum[i] = r2psum[i-1] + r2[i] * 1LL;
  }
  
  c2psum[0] = 0LL;
  for(int i=1; i<=n; i++){
    c2psum[i] = c2psum[i-1] + c2[i] * 1LL;
  }
    
  }
  
  if(n>=3){
    fin[n] = (1-r2[3]) * (1-c2[3]);
    
    for(int i=n-1; i>=3; i--){
      fin[i] = (1-fin[i+1]) * (1-r2[n+3-i]);
    }
    
    for(int i=n+1; i<=2*n-3; i++){
      fin[i] = (1-fin[i-1]) * (1-c2[i+3-n]);
    }
    
    psum[2] = 0LL;
    for(int i=3; i<=2*n-3; i++){
      psum[i] = psum[i-1] + fin[i] * 1LL;
    }
    spsum[2] = 0LL;
    for(int i=3; i<=2*n-3; i++){
      spsum[i] = spsum[i-1] + fin[i] * 1LL * i;
    }
    
  }
  
  vector<ll> vec;
  int q = t.size();
  
  for(int i=0; i<q; i++){
    vec.push_back(getsm(t[i], b[i], l[i], r[i]));
  }
  
  
  return vec;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 22 / 22