Submission #556247

#	Time	Username	Problem	Language	Result	Execution time	Memory
556247		600Mihnea	Team Contest (JOI22_team)	C++17	100 / 100	836 ms	38008 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);
  }
}

vector<int> values[N],aib[N];

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

void upd(int x,int y,int val) {
  for (int i=x;i<=n;i+=i&(-i)) {
    int p=lower_bound(values[i].begin(),values[i].end(),y)-values[i].begin()+1;
    assert(1<=p&&p<(int)aib[i].size());
    assert(values[i][p-1]==y);

    for (int j=p;j<(int)aib[i].size();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)) {

    int low=0,high=(int)values[i].size()-1,p=0;

    while(low<=high){
      int mid=(low+high)/2;
      if(values[i][mid]<=y) {
        p=mid+1;
        low=mid+1;
      }else{
        high=mid-1;
      }
    }

    for (int j=p;j>=1;j-=j&(-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)) {
        values[p].push_back(z);
      }
    }

    for (int i=1;i<=n;i++) {

      sort(values[i].begin(), values[i].end());
      values[i].resize(unique(values[i].begin(), values[i].end())-values[i].begin());
      aib[i].resize((int)values[i].size()+1,-INF);
    }

    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:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     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: 27 / 27