제출 #341415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341415		ivan_tudor	Chessboard (IZhO18_chessboard)	C++14	70 / 100	1196 ms	17576 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct eventhelp{
  int t;
  int l, r;
  int val;
  int type;
};
void add_int(int l, int r, long long val, long long &cnti, long long &cntp){
  int pare, impare;
  int dst = r - l + 1;
  pare = dst/2;
  impare = dst/2;
  if(dst%2 == 1){
    if(l%2 == 0)
      pare++;
    else
      impare++;
  }
  cnti += 1LL * impare * val;
  cntp += 1LL * pare * val;
}
vector<eventhelp> ev;
long long ans = LLONG_MAX;
int n;
bool cmpev(eventhelp a, eventhelp b){
  if(a.t == b.t)
    return a.type > b.type;
  return a.t < b.t;
}
long long imp[N], pr[N];
void solve(int len){
  vector<eventhelp> evc = ev;
  for(int i=len; i<=n;i+=len){
    evc.push_back({i, 0, 0, 0});
  }
  inplace_merge(evc.begin(), evc.begin() + ev.size(), evc.end(), cmpev);
  long long sumi = 0, acti = 0, sump = 0, actp = 0;
  for(auto e:evc){
    if(e.type != 0){
      int fgroup = (e.l - 1)/len + 1;
      int lgroup = (e.r - 1)/len + 1;
      if(fgroup  + 1 <= lgroup - 1){
        add_int(fgroup, lgroup, 1LL* e.val * len, sumi, sump);
        add_int(fgroup, lgroup, 1LL* e.type * len, acti, actp);
      }
      if(fgroup != lgroup){
        add_int(fgroup, fgroup, 1LL * e.val * (fgroup*len - e.l + 1), sumi, sump);
        add_int(fgroup, fgroup, 1LL * e.type * (fgroup*len - e.l + 1), acti, actp);

        add_int(lgroup, lgroup, 1LL * e.val * (e.r - (lgroup - 1)*len), sumi, sump);
        add_int(lgroup, lgroup, 1LL * e.type * (e.r - (lgroup - 1)*len), acti, actp);
      }
      if(fgroup == lgroup){
        add_int(fgroup, fgroup, 1LL * e.val * (e.r - e.l + 1), sumi, sump);
        add_int(fgroup, fgroup, 1LL * e.type * (e.r - e.l + 1), acti, actp);
      }
    }
    else{
      long long csumi, csump;
      csumi = sumi - acti * (n - e.t);
      csump = sump - actp * (n - e.t);
      imp[e.t/len] = csumi;
      pr[e.t/len] =csump;

    }
  }
  long long fans = 0, sans = 0;
  for(int i = 1; i<=n/len;i++){
    long long ci, cp;
    ci = imp[i] - imp[i-1];
    cp = pr[i] - pr[i -1];
    int nrp = (n/len)/2, nri = n/len - nrp;
    if(i %2 == 1){
      fans += 1LL*len*len*nri - ci + cp;
      sans += 1LL*len*len*nrp - cp + ci;
    }
    else{
      sans += 1LL*len*len*nri - ci + cp;
      fans += 1LL*len*len*nrp - cp + ci;
    }
  }
  ans = min(ans, sans);
  ans = min(ans, fans);
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int k;
  cin>>n>>k;
  for(int i=1;i<=k;i++){
    int x1, y1, x2, y2;
    cin>>x1>>y1>>x2>>y2;
    ev.push_back({x1, y1, y2, n - x1 + 1, 1});
    ev.push_back({x2, y1, y2,-(n - x2), -1});
  }
  sort(ev.begin(), ev.end(), cmpev);
  for(int d = 1; d<n; d++){
    if(n%d == 0)
      solve(d);
  }
  cout<<ans;
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 0 / 30