제출 #286693

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

teams

#include <bits/stdc++.h>
#include "teams.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<ll> seg[2000009];
void add(ll v, ll tl, ll tr, ll idx, ll val){
    seg[v].pb(val);
    if(tl == tr) return;
    if(idx <= (tl+tr)/2)
        add(2*v, tl, (tl+tr)/2, idx, val);
    else
        add(2*v+1, (tl+tr)/2+1, tr, idx, val);
}
int get(ll v, ll tl, ll tr, ll l, ll r, ll val){
    if(tr < l || r < tl)
        return 0;
    else if(l <= tl && tr <= r){
        return seg[v].end()-lower_bound(all(seg[v]), val);
    }
    else{
        return get(2*v, tl, (tl+tr)/2, l, r, val) + get(2*v+1, (tl+tr)/2+1, tr, l, r, val);
    }
}
ll n;
void init(int N, int A[], int B[]){
    n = N;
    for(ll i = 0; i < N; ++i){
        add(1, 1, N, A[i], B[i]);
    }
    for(ll i = 1; i <= 4*n+5; ++i)
        sort(all(seg[i]));
}
int can(int M, int K[]){
    sort(K, K+M);
    vector<ll> dp(M);
    vector<ll> use;
    for(ll i = 0; i < M; ++i){
        dp[i] = get(1, 1, n, 1, K[i], K[i])-K[i];
        while(use.size() >= 2){
            ll v1 = dp[use[use.size()-2]] + get(1, 1, n, K[use[use.size()-2]]+1, K[i], K[i]);
            ll v2 = dp[use[use.size()-1]] + get(1, 1, n, K[use[use.size()-1]]+1, K[i], K[i]);
            if(v1 <= v2)
                use.pop_back();
            else
                break;
        }
        if(use.size())
            dp[i] = min(dp[i], dp[use.back()] + get(1, 1, n, K[use.back()]+1, K[i], K[i])-K[i]);
        use.pb(i);
        if(dp[i] < 0){
            return 0;
        }
    }
    return 1;
}

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

teams.cpp: In function 'int get(ll, ll, ll, ll, ll, ll)':
teams.cpp:29:28: warning: conversion from '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   29 |         return seg[v].end()-lower_bound(all(seg[v]), val);
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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