Submission #556241

#	Time	Username	Problem	Language	Result	Execution time	Memory
556241		600Mihnea	Team Contest (JOI22_team)	C++17	73 / 100	2083 ms	166084 KiB

team

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

struct T {
  int x;
  int y;
  int z;
  int tx;
  int ty;
  int tz;
};

bool cmp_x_inv(T a,T b) {
  return a.x>b.x;
}

typedef long long ll;
const int N=150000+7;
const int INF=(int)1e9+7;
int n,zm[N],invy[N],invz[N],value[N];
T a[N];
int aib1[N];

void clr1() {
  for (int i=1;i<=n;i++) aib1[i]=-INF;
}

int get1(int i) {
  int sol=-INF;
  while (i) {
    sol=max(sol,aib1[i]);
    i-=i&(-i);
  }
  return sol;
}

void upd1(int i,int x) {
  while (i<=n){
    aib1[i]=max(aib1[i],x);
    i+=i&(-i);
  }
}

unordered_map<int, int> aib[N];
int dim[N];

void clr() {
  for (int i=1;i<=n;i++) aib[i].clear(),dim[i]=0;
}

void upd(int x,int y,int val) {
  for (int i=x;i<=n;i+=i&(-i)) {
    for (int j=y;j<=n;j+=j&(-j)) {
      aib[i][j]=max(aib[i][j],val);
    }
  }
}

int get(int x,int y) {
  int sol=-INF;
  for (int i=x;i>=1;i-=i&(-i)) {
    for (int j=y;j>=1;j-=j&(-j)) {
      if (aib[i].count(j)) {
        sol=max(sol,aib[i][j]);
      }
    }
  }
  return sol;
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif

  home=0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  cin>>n;
  for (int i=1;i<=n;i++) {
    cin>>a[i].x>>a[i].y>>a[i].z;
  }
  sort(a+1,a+n+1,cmp_x_inv);
  {
    map<int, int> tx,ty,tz;
    for (int i=1;i<=n;i++) tx[a[i].x]=0,ty[a[i].y]=0,tz[a[i].z]=0;
    int ind;
    ind=0; for (auto &it:tx)it.second=++ind;
    ind=0; for (auto &it:ty)it.second=++ind, invy[ind]=it.first;
    ind=0; for (auto &it:tz)it.second=++ind, invz[ind]=it.first;
    for (int i=1;i<=n;i++) a[i].tx=tx[a[i].x], a[i].ty=ty[a[i].y], a[i].tz=tz[a[i].z];
  }
  int print=-1;

  for (int ITER=0;ITER<2;ITER++) {
    clr1();
    clr();

    for (int i=n;i>=1;i--) { /// optimize using aib
      zm[i]=get1(a[i].ty-1);
      upd1(a[i].ty,a[i].tz);
      if (zm[i]<=a[i].tz) zm[i]=-INF;

      if (1<=zm[i]&&zm[i]<=n) value[i]=invz[zm[i]]+a[i].y; else assert(zm[i]==-INF);
    }

    for (int i=1;i<=n;i++) {
      if(zm[i]==-INF) continue;
      int y=n+1-a[i].ty,z=n+1-zm[i];
      for (int p=y;p<=n;p+=p&(-p)) {
        dim[p]++;
      }
    }
    for (int i=1;i<=n;i++) aib[i].rehash(5*dim[i]);

    int last=n;
    while(last>=1){
      int first=last;
      while(first-1>=1&&a[first-1].x==a[first].x) first--;

      for (int i=first;i<=last;i++) {
        print=max(print,get(n-a[i].ty,n-a[i].tz)+a[i].x);
      }

      for (int i=first;i<=last;i++) {
        if (zm[i]!=-INF) {
          upd(n+1-a[i].ty,n+1-zm[i],value[i]);
        }
      }
      last=first-1;
    }
    for (int i=1;i<=n;i++) swap(a[i].y,a[i].z), swap(a[i].ty,a[i].tz), swap(invz[i],invy[i]);
  }

  cout<<print<<"\n";
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:118:25: warning: unused variable 'z' [-Wunused-variable]
  118 |       int y=n+1-a[i].ty,z=n+1-zm[i];
      |                         ^
team.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 27