Submission #276731

#	Time	Username	Problem	Language	Result	Execution time	Memory
276731		stoyan_malinin	Teams (IOI15_teams)	C++14	100 / 100	1690 ms	379644 KiB

teams

#include "teams.h"
//#include "grader.cpp"

#include <set>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 5e5 + 5;

struct SegmentTree
{
    int val;
    SegmentTree *L, *R;

    SegmentTree()
    {
        this->val = 0;

        this->L = nullptr;
        this->R = nullptr;
    }

    void copyFrom(SegmentTree *other)
    {
        val = other->val;
    }

    void build(int l, int r)
    {
        if(l==r) return;

        L = new SegmentTree();
        R = new SegmentTree();

        L->build(l, (l+r)/2);
        R->build((l+r)/2+1, r);
    }

    int query(int ql, int qr, int l, int r)
    {
        if(l>=ql && r<=qr) return val;
        if(r<ql || l>qr) return 0;

        return L->query(ql, qr, l, (l+r)/2) + R->query(ql, qr, (l+r)/2+1, r);
    }

    void update(int q, int change, SegmentTree *other, int l, int r)
    {
        copyFrom(other);
        //cout << l << " " << r << " -> " << q << '\n';

        if(l==r && l==q)
        {
            val += change;
            return;
        }

        if(l<=q && q<=(l+r)/2)
        {
            L = new SegmentTree();
            L->update(q, change, other->L, l, (l+r)/2);
        }
        else
        {
            L = other->L;
        }

        if((l+r)/2+1<=q && q<=r)
        {
            R = new SegmentTree();
            R->update(q, change, other->R, (l+r)/2+1, r);
        }
        else
        {
            R = other->R;
        }

        val = L->val + R->val;
    }
};

struct Event
{
    int type;
    int pos;

    pair <int, int> info;

    Event(){}
    Event(int type, int pos,  pair <int, int> info)
    {
        this->type = type;
        this->pos = pos;

        this->info = info;
    }
};

bool operator <(Event A, Event B)
{
    if(A.pos!=B.pos) return A.pos<B.pos;
    return A.type<B.type;
}

int n;
int *a, *b;

long long dp[MAXN];
SegmentTree *T[MAXN];
vector <int> start2End[MAXN];

SegmentTree* createTree()
{
    return new SegmentTree();
}

int getInside(int x1, int x2, int y1, int y2)
{
    if(x1>x2 || y1>y2) return 0;

    int ans = T[x2]->query(y1, y2, 1, n);
    if(x1!=0) ans -= T[x1-1]->query(y1, y2, 1, n);

    return ans;
}

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

    for(int i = 0;i<n;i++)
        start2End[ a[i] ].push_back(b[i]);

    T[0] = createTree();
    T[0]->build(1, n);

    for(int i = 1;i<=n;i++)
    {
        T[i] = T[i-1];
        for(int x: start2End[i])
        {
            SegmentTree *buff = createTree();
            buff->update(x, +1, T[i], 1, n);

            T[i] = buff;
        }
    }

    /*
    while(true)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;

        cout << getInside(x1, x2, y1, y2) << '\n';
    }
    */
}

int slowSolve(int M, int K[])
{
    multiset <pair <int, int>> s;
    vector <Event> v;

    for(int i = 0;i<n;i++)
    {
        v.push_back(Event(0, a[i], {b[i], a[i]}));
        v.push_back(Event(2, b[i], {b[i], a[i]}));
    }
    for(int i = 0;i<M;i++)
    {
        v.push_back(Event(1, K[i], {K[i], K[i]}));
    }

    sort(v.begin(), v.end());
    //for(Event e: v) cout << e.type << " -> " << e.info.first << " " << e.info.second << '\n';

    for(Event e: v)
    {
        if(e.type==0)
        {
            s.insert(e.info);
        }
        else if(e.type==1)
        {
            if(s.size()<e.info.first) return 0;
            for(int rem = 0;rem<e.info.first;rem++) s.erase(s.find(*s.begin()));
        }
        else if(e.type==2)
        {
            if(s.find(e.info)!=s.end()) s.erase(s.find(e.info));
        }

        //cout << e.type << " -> " << e.info.first << " " << e.info.second << " || " << s.size() << '\n';
    }

    return 1;
}

long long eval(int i, int j, int K[])
{
    return dp[j] + getInside(K[j]+1, K[i], K[i], n) - K[i];
}

bool quickCheck(int M, int K[])
{
    int sum = 0;
    for(int i = 0;i<M;i++)
    {
        sum += K[i];
        if(sum>n) return true;
    }

    return false;
}

int can(int M, int K[])
{
    //if(M>sqrt(n)) return slowSolve(M, K);
    if(quickCheck(M, K)==true) return 0;

    sort(K, K+M);
    for(int i = 0;i<=M;i++) dp[i] = 0;

    vector <int> inds;

    for(int i = 0;i<M;i++)
    {
        dp[i] = getInside(1, K[i], K[i], n) - K[i];
        while(inds.size()>=2 && eval(i, inds[inds.size()-2], K)<=eval(i, inds[inds.size()-1], K)) inds.pop_back();

        for(int j = inds.size()-1;j>=max(0, int(inds.size())-5);j--)
            dp[i] = min(dp[i], eval(i, inds[j], K));

        inds.push_back(i);
    }

    long long minVal = MAXN;
    for(int i = 0;i<M;i++) minVal = min(minVal, dp[i]);

    if(minVal<0) return 0;
    return 1;
}
/*
4
1 2
2 3
2 3
2 4
2
2
1 3
2
1 1
*/

Compilation message (stderr)

teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:95:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
   95 |     {
      |     ^
teams.cpp:91:21: note: shadowed declaration is here
   91 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:95:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
   95 |     {
      |     ^
teams.cpp:89:9: note: shadowed declaration is here
   89 |     int pos;
      |         ^~~
teams.cpp:95:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
   95 |     {
      |     ^
teams.cpp:88:9: note: shadowed declaration is here
   88 |     int type;
      |         ^~~~
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:100:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:91:21: note: shadowed declaration is here
   91 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:100:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:89:9: note: shadowed declaration is here
   89 |     int pos;
      |         ^~~
teams.cpp:100:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:88:9: note: shadowed declaration is here
   88 |     int type;
      |         ^~~~
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:100:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:91:21: note: shadowed declaration is here
   91 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:100:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:89:9: note: shadowed declaration is here
   89 |     int pos;
      |         ^~~
teams.cpp:100:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:88:9: note: shadowed declaration is here
   88 |     int type;
      |         ^~~~
teams.cpp: In function 'int slowSolve(int, int*)':
teams.cpp:192:24: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  192 |             if(s.size()<e.info.first) return 0;
      |                ~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:238:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  238 |         for(int j = inds.size()-1;j>=max(0, int(inds.size())-5);j--)
      |                     ~~~~~~~~~~~^~

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