Submission #155936

#TimeUsernameProblemLanguageResultExecution timeMemory
155936junodeveloperTeams (IOI15_teams)C++14
0 / 100
1148 ms144580 KiB
#include "teams.h" #include <bits/stdc++.h> #define sz(x) (int)x.size() using namespace std; const int maxn=500000; const int tmax=20*maxn+4*maxn; int n,m; int root[maxn+10]; int tree[tmax],tl[tmax],tr[tmax],tcnt; vector<int> vx,vy; int build(int s,int e) { int u=++tcnt; tree[u]=0; if(s==e) return u; int mid=(s+e)/2; tl[u]=build(s,mid); tr[u]=build(mid+1,e); return u; } int update(int u,int s,int e,int p,int x) { if(p<s||e<p) return u; int nu=++tcnt; tree[nu]=tree[u]+x; if(s==e) return nu; int mid=(s+e)/2; tl[nu]=update(tl[u],s,mid,p,x); tr[nu]=update(tr[u],mid+1,e,p,x); return nu; } int query(int u,int s,int e,int l,int r) { if(l>r) return 0; if(e<l||r<s) return 0; if(l<=s&&e<=r) return tree[u]; int mid=(s+e)/2; return query(tl[u],s,mid,l,r)+query(tr[u],mid+1,e,l,r); } void init(int N, int A[], int B[]) { n=N; vector<int> a; int i,j; for(i=0;i<n;i++)a.push_back(i); sort(a.begin(),a.end(),[&](int x,int y) { return B[x]<B[y]; }); for(i=0;i<n;i++) { vx.push_back(A[a[i]]); vy.push_back(B[a[i]]); } sort(vx.begin(),vx.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end()); root[n]=build(0,sz(vx)-1); for(i=n-1;i>=0;i--) { j=lower_bound(vx.begin(),vx.end(),A[a[i]])-vx.begin(); root[i]=update(root[i+1],0,sz(vx)-1,j,1); } } int can(int M, int K[]) { m=M; int i,j,k; sort(K,K+m); long long mx=-1e18,q1,q2,cur=0; for(i=0;i<m;i++) { j=lower_bound(vy.begin(),vy.end(),K[i])-vy.begin(); k=lower_bound(vx.begin(),vx.end(),K[i]+1)-vx.begin()-1; q1=query(root[j],0,sz(vx)-1,0,k); if(i) { k=lower_bound(vx.begin(),vx.end(),K[i-1]+1)-vx.begin()-1; q2=query(root[j],0,sz(vx)-1,0,k); } else q2=0; cur=K[i]-q1+max(0ll,cur+q2); mx=max(mx,cur); } return mx<=0; }

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:53:45: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   j=lower_bound(vx.begin(),vx.end(),A[a[i]])-vx.begin();
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:64:42: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   j=lower_bound(vy.begin(),vy.end(),K[i])-vy.begin();
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:65:55: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   k=lower_bound(vx.begin(),vx.end(),K[i]+1)-vx.begin()-1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:68:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
    k=lower_bound(vx.begin(),vx.end(),K[i-1]+1)-vx.begin()-1;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...