제출 #536722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536722		ivan24	팀들 (IOI15_teams)	C++14	77 / 100	4091 ms	315640 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
 
using ll = 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){
        /*
        cout << "queried: " << curt << "\n";
        for (auto i: v) cout << i << " ";
        cout << endl;
        for (auto i: t) cout << i << " ";
        cout << endl;
        */
        auto itr = upper_bound(t.begin(),t.end(),curt);
        //ll idx = distance(t.begin(),itr)-1;
        ll idx = (itr-t.begin())-1;
        //cout << v[idx] << endl;
        return v[idx];
    }
    ll lst_qry(){
        return v.back();
    }
    void inc_update (ll vn, ll tn){
        if (t.back() != tn){
            v.push_back(lst_qry()+vn);
            t.push_back(tn);
        }else{
            v[v.size()-1] += vn;
        }
    }
    void change_update (ll vn, ll tn){
        if (t.back() != tn){
            v.push_back(vn);
            t.push_back(tn);
        }else{
            v[v.size()-1] = vn;
        }
    }
    PNode (){ v = vi{0}; t = vi{0}; }
};
 
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 << " " << t << " , " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
        }
    }
    ll query (ll i, ll l, ll r, ll ql, ll qr, ll t){
        //cout << i << " " << l << " " << r << " " << ql << " " << qr << endl;
        if (qr >= r && l >= ql){
            /*
            cout << "queried: \n";
            cout << "params: " << i << " " << l << " " << r << endl;
            cout << "result: " << st[i].qry(t) << endl;
            */
            return st[i].qry(t);
        }else if (l > qr || ql > r){
            return 0;
        }else{
            ll m = (l+r)/2;
            ll lres = 0, rres = 0;
            if (!(l > qr || ql > m)) lres = query(left(i),l,m,ql,qr,t);
            if (!(m+1 > qr || ql > r)) 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);
    }
}
 
vi ctr,vals,byBucket;
 
int can(int m, int k[]) {
    sort(k,k+m);
    ll sum = 0;
    for (ll i = 0; m > i; i++) sum += k[i];
    if (sum > n) return 0;
    vi().swap(ctr);
    ctr.push_back(k[0]);
    for (ll i = 1; m > i; i++){
        if (k[i] != k[i-1]) ctr.push_back(0);
        ctr[ctr.size()-1] += k[i];
    }
    vi().swap(vals);
    vals.push_back(k[0]);
    for (ll i = 1; m > i; i++){
        if (k[i] != k[i-1]) vals.push_back(k[i]);
    }
    vals.push_back(n+1);
    vi byBucket;
    byBucket.assign(vals.size(),0);
    /*
    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;
            ll rmv = st.query(vals[j],vals[j+1]-1,vals[i])-byBucket[j];
            //cout << vals[j] << " " << vals[j+1] << " " << vals[i] << ": " << rmv << endl;
            //cout << "itr: " << itr->F << " " << itr->S << endl;
            rmv = min(rmv,ctr[i]);
            ctr[i] -= rmv;
            byBucket[j] += rmv;
        }
        if (ctr[i] > 0) return 0;
        /*
        cout << itr->F << " " << itr->S << endl;
        for (auto i: byBucket) cout << i << " ";
        cout << endl;
        */
    }
    //cout << "1\n";
	return 1;
}

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

teams.cpp: In member function 'll PNode::qry(ll)':
teams.cpp:34:33: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'll' {aka 'int'} may change value [-Wconversion]
   34 |         ll idx = (itr-t.begin())-1;
      |                  ~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:149:8: warning: declaration of 'byBucket' shadows a global declaration [-Wshadow]
  149 |     vi byBucket;
      |        ^~~~~~~~
teams.cpp:130:13: note: shadowed declaration is here
  130 | vi ctr,vals,byBucket;
      |             ^~~~~~~~
teams.cpp:157:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  157 |     for (ll i = 0; vals.size() > i+1; i++){
      |                    ~~~~~~~~~~~~^~~~~
teams.cpp:158:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  158 |         for (ll j = i; vals.size() > j+1; j++){
      |                        ~~~~~~~~~~~~^~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23