제출 #535421

#제출 시각아이디문제언어결과실행 시간메모리
535421ivan24팀들 (IOI15_teams)C++14
0 / 100
4033 ms320468 KiB
#include "teams.h" #include<bits/stdc++.h> using namespace std; using ll = long long int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; typedef vector<ii> vii; typedef vector<vii> vvii; #define F first #define S second ll min (ll x, ll y){ return ((x < y) ? x : y); } ll max (ll x, ll y){ return ((x > y) ? x : y); } struct PNode { vi v,t; ll qry (ll curt){ if (t.size() == 0) return 0; if (t[0] > curt) return 0; auto itr = upper_bound(t.begin(),t.end(),curt); ll idx = distance(t.begin(),itr)-1; return v[idx]; } ll lst_qry(){ if (v.size() == 0) return 0; return v.back(); } void inc_update (ll vn, ll tn){ if (t.size() == 0){ v.push_back(vn); t.push_back(tn); }else if (t.back() != tn){ v.push_back(vn); t.push_back(tn); }else{ v[v.size()-1] += vn; } } void change_update (ll vn, ll tn){ if (t.size() == 0){ v.push_back(vn); t.push_back(tn); }else if (t.back() != tn){ v.push_back(vn); t.push_back(tn); }else{ v[v.size()-1] = vn; } } PNode (){ v = vi(); t = vi(); } }; class SegTree { private: vector<PNode> st; ll n; ll left (ll x){ return (x << 1) ; } ll right (ll x){ return (x << 1) + 1; } void update (ll i, ll l, ll r, ll idx, ll inc, ll t){ // assumed that t is updated increasingly if (r >= idx && idx >= l){ if (l == r){ st[i].inc_update(inc,t); }else{ //cout << i << " " << l << " -> " << r << " : " << st[i].lst_qry() << endl; ll m = (l+r)/2; update(left(i),l,m,idx,inc,t); update(right(i),m+1,r,idx,inc,t); st[i].change_update(st[left(i)].lst_qry()+st[right(i)].lst_qry(),t); } //cout << i << " " << l << " -> " << r << " : " << st[i].lst_qry() << endl; } } ll query (ll i, ll l, ll r, ll ql, ll qr, ll t){ if (qr >= r && l >= ql){ //cout << i << " " << l << " " << r << endl; return st[i].qry(t); }else if (l > qr || ql > r){ return 0; }else{ //cout << i << " " << l << " " << r << endl; ll m = (l+r)/2; ll lres = query(left(i),l,m,ql,qr,t); ll rres = query(right(i),m+1,r,ql,qr,t); return lres+rres; } } public: SegTree (){} SegTree(ll _n): n(_n){ st.resize(4*n); } void update (ll idx, ll inc, ll t){ update(1,0,n-1,idx,inc,t); } ll query (ll ql, ll qr, ll t){ return query(1,0,n-1,ql,qr,t); } }; SegTree st; ll n; void init(int _n, int a[], int b[]) { n = _n; st = SegTree(n+1); vii itvls; for (ll i = 0; n > i; i++) itvls.emplace_back(a[i],b[i]); sort(itvls.begin(),itvls.end()); for (auto i: itvls){ //cout << i.F << " " << i.S << endl; st.update(i.S,1,i.F); } } int can(int m, int k[]) { map<ll,ll> ctr; for (ll i = 0; m > i; i++){ if (ctr.find(k[i]) == ctr.end()) ctr[k[i]] = 0; ctr[k[i]]++; } vi vals; for (auto i: ctr){ vals.push_back(i.F); } vals.push_back(n-1); vi byBucket; byBucket.assign(vals.size(),0); auto itr = ctr.begin(); /* cout << itr->F << " " << itr->S << endl; cout << "vals:\n"; for (auto i: vals) cout << i << " "; cout << endl; */ for (ll i = 0; vals.size() > i+1; i++){ for (ll j = i; vals.size() > j+1; j++){ //cout << "i: " << i << " j: " << j << endl; if (itr->S == 0) break; ll rmv = st.query(vals[j],vals[j+1]-1,vals[i])-byBucket[j]; rmv = min(rmv,itr->S); itr->S -= rmv; byBucket[i] += rmv; } //cout << itr->F << " " << itr->S << endl; //for (auto i: byBucket) cout << i << " "; //cout << endl; itr++; } for (auto i: ctr){ if (i.S != 0) return 0; } return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int can(int, int*)':
teams.cpp:145:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  145 |     for (ll i = 0; vals.size() > i+1; i++){
      |                    ~~~~~~~~~~~~^~~~~
teams.cpp:146:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  146 |         for (ll j = i; vals.size() > j+1; j++){
      |                        ~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...