제출 #220788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220788		VEGAnn	Teams (IOI15_teams)	C++14	34 / 100	4109 ms	365256 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
vector<pii> events, vc;
int n, f[N];

struct seg_tree{
    seg_tree *l, *r;
    int sm;

    seg_tree(): l(0), r(0), sm(0) {}
    seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}

    void build(int tl, int tr){
        sm = 0;

        if (tl == tr) return;

        int md = (tl + tr) >> 1;

        l = new seg_tree();
        r = new seg_tree();

        l -> build(tl, md);
        r -> build(md + 1, tr);
    }

    void update(int tl, int tr, int ps){
        sm++;

        if (tl == tr) return;

        int md = (tl + tr) >> 1;

        if (ps <= md){
            l = new seg_tree(l);
            l -> update(tl, md, ps);
        } else {
            r = new seg_tree(r);
            r -> update(md + 1, tr, ps);
        }
    }

    int sum(int tl, int tr, int ql, int qr){
        if (ql > qr) return 0;

        if (ql == tl && qr == tr) return sm;

        int md = (tl + tr) >> 1;

        return l -> sum(tl, md, ql, min(qr, md)) + r -> sum(md + 1, tr, max(md + 1, ql), qr);
    }
};

seg_tree *root[N];

void init(int N, int A[], int B[]) {
    n = N;

    for (int i = 0; i < n; i++)
        vc.PB(MP(A[i], B[i]));

    sort(all(vc));

    root[n] = new seg_tree();
    root[n] -> build(1, n);

    for (int i = n - 1; i >= 0; i--){
        root[i] = new seg_tree(root[i + 1]);
        root[i] -> update(1, n, vc[i].sd);
    }
}

int calc(int x1, int y1, int x2, int y2){
    int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
    int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();

    cerr << (root[lf] -> sum(1, n, y1, y2)) << " " << (root[rt] -> sum(1, n, y1, y2)) << '\n';

    return (root[lf] -> sum(1, n, y1, y2)) - (root[rt] -> sum(1, n, y1, y2));
}

int can(int M, int K[]) {
    sort(K, K + M);

    events.clear();

    ll sum = 0ll;

    for (int i = 0; i < M; ){
        int j = i;
        events.PB(MP(K[i], 0));

        while (j < M && K[i] == K[j]){
            sum += K[j];
            events.back().sd++;
            j++;
        }

        i = j;
    }

    if (sum > ll(n)) return 0;

    for (int it = 0; it < sz(events); it++){
        pii cr = events[it];

        int cur_kol = cr.ft * cr.sd;

        f[it] = calc(1, cr.ft, cr.ft, n) - cur_kol;

        for (int pr = 0; pr < it; pr++)
            f[it] = min(f[it], f[pr] + calc(events[pr].ft + 1, cr.ft, cr.ft, n) - cur_kol);

        if (f[it] < 0)
            return 0;
    }

    return 1;
}

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

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:67:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:13:11: note: shadowed declaration is here
 const int N = 500100;
           ^
teams.cpp: In function 'int calc(int, int, int, int)':
teams.cpp:85:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
     int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp:86:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
     int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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