Submission #276715

#	Time	Username	Problem	Language	Result	Execution time	Memory
276715		stoyan_malinin	Teams (IOI15_teams)	C++14	77 / 100	1366 ms	524292 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;

    int l, r;
    SegmentTree *L, *R;

    SegmentTree(){}
    SegmentTree(int l, int r)
    {
        this->val = 0;
        this->l = l;
        this->r = r;

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

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

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

        L = new SegmentTree(l, (l+r)/2);
        R = new SegmentTree((l+r)/2+1, r);

        L->build();
        R->build();
    }

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

        return L->query(ql, qr) + R->query(ql, qr);
    }

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

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

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

        if(other->R->l<=q && q<=other->R->r)
        {
            R = new SegmentTree(other->R->l, other->R->r);
            R->update(q, change, other->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;

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

SegmentTree* createTree()
{
    return new SegmentTree(1, n);
}

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

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

    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();

    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]);

            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;
}

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

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

    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();

        if(inds.size()>0) dp[i] = min(dp[i], eval(i, inds.back(), K));
        inds.push_back(i);
    }

    int 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 'SegmentTree::SegmentTree(int, int)':
teams.cpp:23:5: warning: declaration of 'r' shadows a member of 'SegmentTree' [-Wshadow]
   23 |     {
      |     ^
teams.cpp:18:12: note: shadowed declaration is here
   18 |     int l, r;
      |            ^
teams.cpp:23:5: warning: declaration of 'l' shadows a member of 'SegmentTree' [-Wshadow]
   23 |     {
      |     ^
teams.cpp:18:9: note: shadowed declaration is here
   18 |     int l, r;
      |         ^
teams.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
teams.cpp:30:5: warning: declaration of 'r' shadows a member of 'SegmentTree' [-Wshadow]
   30 |     }
      |     ^
teams.cpp:18:12: note: shadowed declaration is here
   18 |     int l, r;
      |            ^
teams.cpp:30:5: warning: declaration of 'l' shadows a member of 'SegmentTree' [-Wshadow]
   30 |     }
      |     ^
teams.cpp:18:9: note: shadowed declaration is here
   18 |     int l, r;
      |         ^
teams.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
teams.cpp:30:5: warning: declaration of 'r' shadows a member of 'SegmentTree' [-Wshadow]
   30 |     }
      |     ^
teams.cpp:18:12: note: shadowed declaration is here
   18 |     int l, r;
      |            ^
teams.cpp:30:5: warning: declaration of 'l' shadows a member of 'SegmentTree' [-Wshadow]
   30 |     }
      |     ^
teams.cpp:18:9: note: shadowed declaration is here
   18 |     int l, r;
      |         ^
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:102:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  102 |     {
      |     ^
teams.cpp:98:21: note: shadowed declaration is here
   98 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:102:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  102 |     {
      |     ^
teams.cpp:96:9: note: shadowed declaration is here
   96 |     int pos;
      |         ^~~
teams.cpp:102:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  102 |     {
      |     ^
teams.cpp:95:9: note: shadowed declaration is here
   95 |     int type;
      |         ^~~~
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:107:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  107 |     }
      |     ^
teams.cpp:98:21: note: shadowed declaration is here
   98 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:107:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  107 |     }
      |     ^
teams.cpp:96:9: note: shadowed declaration is here
   96 |     int pos;
      |         ^~~
teams.cpp:107:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  107 |     }
      |     ^
teams.cpp:95:9: note: shadowed declaration is here
   95 |     int type;
      |         ^~~~
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:107:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  107 |     }
      |     ^
teams.cpp:98:21: note: shadowed declaration is here
   98 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:107:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  107 |     }
      |     ^
teams.cpp:96:9: note: shadowed declaration is here
   96 |     int pos;
      |         ^~~
teams.cpp:107:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  107 |     }
      |     ^
teams.cpp:95:9: note: shadowed declaration is here
   95 |     int type;
      |         ^~~~
teams.cpp: In function 'int slowSolve(int, int*)':
teams.cpp:199: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]
  199 |             if(s.size()<e.info.first) return 0;
      |                ~~~~~~~~^~~~~~~~~~~~~

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