Submission #1017257

#TimeUsernameProblemLanguageResultExecution timeMemory
1017257huutuanTeams (IOI15_teams)C++14
34 / 100
4062 ms32080 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; struct Node{ vector<int> data; void merge(const Node &tl, const Node &tr){ data.resize(tl.data.size()+tr.data.size()); std::merge(tl.data.begin(), tl.data.end(), tr.data.begin(), tr.data.end(), data.begin()); } }; struct SegmentTree{ int n; vector<Node> t; void init(int _n){ n=_n; t.assign(4*n+1, Node()); } void build(int k, int l, int r, pair<int, int> a[]){ if (l==r){ t[k].data.push_back(a[l].first); return; } int mid=(l+r)>>1; build(k<<1, l, mid, a); build(k<<1|1, mid+1, r, a); t[k].merge(t[k<<1], t[k<<1|1]); } int cnt; int count(int k, int val){ return upper_bound(t[k].data.begin(), t[k].data.end(), val)-t[k].data.begin(); } int walk(int k, int l, int r, int L, int R, int val){ if (r<L || R<l) return 0; if (L<=l && r<=R){ int cc=count(k, val); if (cc<cnt){ cnt-=cc; return 0; } } if (l==r) return t[k].data[0]<=val && cnt==1; int mid=(l+r)>>1; int ans=walk(k<<1, l, mid, L, R, val); if (ans) return ans; return walk(k<<1|1, mid+1, r, L, R, val); } } st; const int N=5e5+10; int n, pos[N]; pair<int, int> a[N]; void init(int _N, int _A[], int _B[]) { n=_N; for (int i=1; i<=n; ++i) a[i]={_A[i-1], _B[i-1]}; sort(a+1, a+n+1); // sort(a+1, a+n+1, [&](pair<int, int> x, pair<int, int> y){ // if (x.second!=y.second) return x.second<y.second; // return x.first<y.first; // }); // st.init(n); // st.build(1, 1, n, a); // for (int i=1; i<=n; ++i) pos[i]=n+1; // for (int i=1; i<=n; ++i) pos[a[i].second]=min(pos[a[i].second], i); // for (int i=1; i<n; ++i) pos[i]=min(pos[i], pos[i+1]); } int can(int M, int K[]) { sort(K, K+M); multiset<int> st; for (int i=0, j=1; i<M; ++i){ while (j<=n && a[j].first<=K[i]){ st.insert(a[j].second); ++j; } int cnt=K[i]; while (st.size()){ int tmp=*st.begin(); st.erase(st.begin()); if (tmp>=K[i]){ --cnt; if (cnt==0) break; } } if (cnt) return 0; } // for (int i=1, j=0, cnt=K[0]; i<=n; ++i){ // if (a[i].first<=K[j] && K[j]<=a[i].second){ // --cnt; // if (!cnt){ // ++j; // if (j==M) return 1; // cnt=K[j]; // } // } // } // int cur=1; // for (int i=0; i<M; ++i){ // int k=K[i]; // if (pos[k]==n+1) return 0; // cur=max(cur, pos[k]); // st.cnt=k; // int id=st.walk(1, 1, n, cur, n, k); // if (!id) return 0; // cur=id+1; // } return 1; }

Compilation message (stderr)

teams.cpp: In member function 'int SegmentTree::count(int, int)':
teams.cpp:34:66: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   34 |       return upper_bound(t[k].data.begin(), t[k].data.end(), val)-t[k].data.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:74:18: warning: declaration of 'st' shadows a global declaration [-Wshadow]
   74 |    multiset<int> st;
      |                  ^~
teams.cpp:51:3: note: shadowed declaration is here
   51 | } st;
      |   ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...