제출 #424577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
424577		79brue	팀들 (IOI15_teams)	C++14	0 / 100	601 ms	254712 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

typedef long long ll;

struct segTree{
    vector<int> tree[2000002];

    void init(int i, int l, int r){
        if(l==r){
            sort(tree[i].begin(), tree[i].end());
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i].resize((int)tree[i*2].size() + (int)tree[i*2+1].size());
        merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
    }

    void addPoint(int i, int l, int r, int x, int y){
        if(l==r){
            tree[i].push_back(y);
            return;
        }
        int m = (l+r)>>1;
        if(x <= m) addPoint(i*2, l, m, x, y);
        else addPoint(i*2+1, m+1, r, x, y);
    }

    int query(int i, int l, int r, int s, int e, int vl, int vr){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e){
            return upper_bound(tree[i].begin(), tree[i].end(), vr) - lower_bound(tree[i].begin(), tree[i].end(), vl);
        }
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e, vl, vr) + query(i*2+1, m+1, r, s, e, vl, vr);
    }

    pair<int, int> findLim(int i, int l, int r, int x, int s, int e, int &lim){
        if(l==r) return make_pair(l-1, lim);
        int m = (l+r)>>1;
        if(x>m) return findLim(i*2+1, m+1, r, x, s, e, lim);

        int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
        if(tret <= lim){
            lim -= tret;
            return make_pair(-1, -1);
        }

        auto tmp = findLim(i*2, l, m, x, s, e, lim);
        if(tmp.first >= 0) return tmp;
        return findLim(i*2+1, m+1, r, x, s, e, lim);
    }
} tree;
vector<int> occ[500002];

int n;

void init(int N, int A[], int B[]){
    n = N;
    for(int i=0; i<n; i++) tree.addPoint(1, 1, n, B[i], A[i]);
    tree.init(1, 1, n);

    for(int i=0; i<n; i++) occ[B[i]].push_back(A[i]);
    for(int i=1; i<=n; i++) sort(occ[i].begin(), occ[i].end());
}

int k;
int arr[200002];
stack<pair<int, int> > stk;

int can(int M, int K[]){
    k = M;
    for(int i=1; i<=k; i++) arr[i] = K[i-1];
    sort(arr+1, arr+k+1);

    while(!stk.empty()) stk.pop();
    stk.push(make_pair(0, n));

    for(int i=1; i<=k; i++){
        int x = arr[i], lim = arr[i];
        while(i<k && arr[i] == arr[i+1]){
            i++;
            x += arr[i];
        }

        while(!stk.empty()){
            pair<int, int> tmp = stk.top();
            int ret = tree.query(1, 1, n, lim, tmp.second, tmp.first+1, arr[i]);
            if(ret > x) break;
            stk.pop();
            x -= ret;
            lim = tmp.second+1;
        }

        if(stk.empty()){
            if(x) return false;
            stk.push(make_pair(arr[i], n));
            continue;
        }

        pair<int, int> tmp = tree.findLim(1, 1, n, lim, stk.top().first+1, arr[i], x);
        int bx = tmp.first;

        if(x){
            auto it = lower_bound(occ[bx+1].begin(), occ[bx+1].end(), stk.top().first+1) + (x-1);
            stk.push(make_pair(*it, bx+1));
        }
        stk.push(make_pair(arr[i], bx));
    }

    return true;
}

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

teams.cpp: In member function 'int segTree::query(int, int, int, int, int, int, int)':
teams.cpp:36:68: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   36 |             return upper_bound(tree[i].begin(), tree[i].end(), vr) - lower_bound(tree[i].begin(), tree[i].end(), vl);
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'std::pair<int, int> segTree::findLim(int, int, int, int, int, int, int&)':
teams.cpp:47:67: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   47 |         int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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