Submission #65990

#TimeUsernameProblemLanguageResultExecution timeMemory
65990gnoorTeams (IOI15_teams)C++17
77 / 100
4038 ms367352 KiB
#include "teams.h" #include <algorithm> #include <vector> #include <cstdio> using namespace std; struct node { int val; node *lft,*rgt; node(int _val,node *_l=0,node *_r=0): val(_val),lft(_l),rgt(_r) {} node* insert(int l,int r,int k) { if (k<l||k>=r) return this; if (l+1==r) return new node(this->val+1,lft,rgt); int m=(l+r)>>1; return new node(this->val+1,lft->insert(l,m,k),rgt->insert(m,r,k)); } int query(int l,int r,int ll,int rr) { if (rr<=l||ll>=r) return 0; if (ll<=l&&rr>=r) return this->val; int m=(l+r)>>1; return lft->query(l,m,ll,rr)+rgt->query(m,r,ll,rr); } }; node* root[500100]; int pos[500100]; int n; void init(int N, int A[], int B[]) { n=N; vector<pair<int,int>> student; for (int i=0;i<N;i++) { student.push_back({A[i],B[i]}); } sort(student.begin(),student.end()); root[0]=new node(0); root[0]->lft=root[0]; root[0]->rgt=root[0]; for (int i=1;i<=n;i++) { root[i]=root[i-1]->insert(1,N+1,student[i-1].second); pos[student[i-1].first]=i; } for (int i=1;i<=n;i++) { if (pos[i]==0) pos[i]=pos[i-1]; } } int used[5100]; int can(int M, int K[]) { sort(K,K+M); vector<int> x; for (int i=0;i<M;i++) x.push_back(K[i]); x.resize(unique(x.begin(),x.end())-x.begin()); int nn=x.size(); fill(used,used+nn,0); int res; int ptr=0; int cur; int ptr2; for (int i=0;i<M;i++) { while (x[ptr]<K[i]) ptr++; cur=K[i]; ptr2=ptr; while (cur&&ptr2<nn) { res=root[pos[K[i]]]->query(1,n+1,x[ptr2],(ptr2==nn-1)?n+1:x[ptr2+1])-used[ptr2]; used[ptr2]+=min(res,cur); cur-=min(res,cur); ptr2++; } if (cur!=0) return 0; } return 1; }

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:62:15: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int nn=x.size();
         ~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...