제출 #1125930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125930		ntdaccode	메기 농장 (IOI22_fish)	C++20	67 / 100	1098 ms	41288 KiB

fish

#include<bits/stdc++.h>
#include <vector>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back


using namespace std;

typedef pair<int,long long> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;

int n, m;
long long t[2][2][4 * N], lz[2][2][4 * N];

void add(int cur, int tt, int s, long long val)
{
  t[cur][tt][s] += val;
  lz[cur][tt][s] += val;
}

void lazy(int cur, int tt, int s)
{
  add(cur, tt, s * 2, lz[cur][tt][s]);
  add(cur, tt, s * 2 + 1, lz[cur][tt][s]);
  lz[cur][tt][s] = 0;
}

void upd(int cur, int tt, int s, int l, int r, int u, int v, long long val)
{
  if(u > r || v < l) return ;
  if(u <= l && r <= v) {
    add(cur, tt, s, val);
    return ;
  }
  int mid = (l + r)/2;
  if(l != r && lz[cur][tt][s] != 0) lazy(cur,tt,s);
  upd(cur, tt, s * 2, l, mid, u, v, val);
  upd(cur, tt, s * 2 + 1, mid + 1, r, u, v, val);
  t[cur][tt][s] = max(t[cur][tt][s * 2], t[cur][tt][s * 2 + 1]);
}

long long get(int cur,int tt,int s, int l, int r,int u,int v)
{
  if(u > r || v < l) return 0;
  if(u <= l && r <= v) return t[cur][tt][s];
  int mid = (l + r)/2;
  if(l != r && lz[cur][tt][s] != 0) lazy(cur,tt,s);
  return max(get(cur, tt, s * 2, l, mid, u, v), get(cur, tt, s * 2 + 1, mid + 1, r, u, v));
}



vector<ii> Q[N];
long long f[2][2][N];


long long max_weights(int N, int M,std::vector<int> X ,std::vector<int> Y ,std::vector<int> W )
{
  n = N;
  m = M;
  for(int i = 1;i <= n; i++) Q[i].pb({0,0});
  for(int i = 0;i < m; i++) {
    X[i]++;
    Y[i]++;
    Q[X[i]].pb({Y[i],W[i]});
  }
  for(int i = 1;i <= n; i++) sort(Q[i].begin(), Q[i].end());
  for(int i = 1;i <= n; i++) {
    int u = Q[i].back().first;
    if(u != n) Q[i].pb({n,0});
  }
  int pre, cur;
  for(int i = 2;i <= n; i++) {
    //
    pre = i - 1 & 1, cur = i & 1;
    for(auto[pos,val] : Q[i]) {
      upd(pre, 0, 1, 0, n, pos, n, val);
      upd(pre, 1, 1, 0, n, pos, n, val);
    }


    for(auto[pos,val] : Q[i]) {
        if(pos != 0 && f[cur][1][pos - 1] == 0) {
          long long x = max(get(pre, 0, 1, 0, n, pos - 1, n), get(pre, 1, 1, 0, n, pos - 1, n));
          upd(cur, 1, 1, 0, n, pos - 1, pos - 1, x);
          f[cur][1][pos - 1] = x;
        }
        upd(pre, 0, 1, 0, n, pos, n, -val);
        upd(pre, 1, 1, 0, n, pos, n, -val);
        long long x = max(get(pre, 0, 1, 0, n, pos, n), get(pre, 1, 1, 0, n, pos, n));
        upd(cur, 1, 1, 0, n, pos, pos, x);
        f[cur][1][pos] = x;
       //cout << i << " " << 1 << " " << pos << " " << x << "\n";
    }
    //
    for(auto [pos,val] : Q[i - 1]) {
        upd(pre, 0, 1, 0, n, 0, pos - 1, val);
        //if(i == 2) cerr << val << " " << pos << "\n";
    }
    reverse(Q[i - 1].begin(), Q[i - 1].end());
    for(auto [pos,val] : Q[i - 1]) {
      long long x = max(get(pre, 0, 1, 0, n, 0, pos),get(pre, 1, 1, 0, n, 0, pos));
      upd(cur, 0, 1, 0, n, pos, pos, x);
      f[cur][0][pos] = x;
      //cout << i << " " << 0 <<  " " <<  pos << " " << x << "\n";
      upd(pre, 0, 1, 0, n, 0, pos - 1, -val);
    }
    reverse(Q[i - 1].begin(), Q[i - 1].end());

    for(auto[pos,val] : Q[i - 1]) {
      upd(pre, 1, 1, 0, n, pos, pos, -f[pre][1][pos]);
      f[pre][1][pos] = 0;
      if(pos != 0 && f[pre][1][pos - 1] != 0) {
        upd(pre, 1, 1, 0, n, pos - 1, pos - 1, -f[pre][1][pos - 1]);
        f[pre][1][pos - 1] = 0;
      }
    }
    if(i != 2) {
      for(auto[pos,val] : Q[i - 2]) {
         upd(pre, 0, 1, 0, n, pos, pos, -f[pre][0][pos]);
         f[pre][0][pos] = 0;
      }
    }
  }
  long long kq = max(t[n & 1][0][1],t[n & 1][1][1]);
  return kq;
}

• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16