제출 #276864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
276864		stoyan_malinin	팀들 (IOI15_teams)	C++14	0 / 100	4053 ms	373264 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];
}

int getBetter(int i, int j, int M, int K[])
{
    //if(eval(M-1, i, K)>=eval(M-1, j, K)) return n+5;

    int l = 1, r = n;
    SegmentTree *Tadd = T[ K[j] ], *Trem = T[ K[i] - 1 ];

    long long val = dp[j] - dp[i];
    //if(Tadd->query(n, n, 1, n)-Trem->query(n, n, 1, n)>val) return n + 5;

    while(l!=r)
    {
        long long currVal = Tadd->R->val - Trem->R->val;

        if(currVal<=val)
        {
            val -= currVal ;

            Tadd = Tadd->L;
            Trem = Trem->L;
            r = (l+r)/2;
        }
        else
        {
            Tadd = Tadd->R;
            Trem = Trem->R;
            l = (l+r)/2 + 1;
        }
    }

    Tadd = T[ K[j] ];
    Trem = T[ K[i] - 1 ];

    val = dp[j] - dp[i];
    for(int ind = 1;ind<=n;ind++)
    {
        if(Tadd->query(ind, n, 1, n)-Trem->query(ind, n, 1, n)<=val) return ind;
    }

    return n + 5;
    cout << 1/0 << '\n';
}

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

void addInd(set <int> &s, set <pair <int, int>> &toRemove, int x, int M, int K[])
{
    s.insert(x);
    auto it1 = s.find(x);

    if(it1!=s.begin())
    {
        auto it2 = it1;
        it2--;

        toRemove.insert({getBetter(*it2, *it1, M, K), *it1});
    }
}

void remInd(set <int> &s, set <pair <int, int>> &toRemove, int x, int M, int K[])
{
    auto it1 = s.find(x);
    if(it1==s.end()) return;

    it1++;
    s.erase(x);

    if(s.size()==0 || it1!=s.end())
    {
        auto it2 = it1;
        it2--;

        toRemove.insert({getBetter(*it2, *it1, M, K), *it1});
    }
}

int last(set <int> &s)
{
    auto it = s.end();
    it--;

    return *it;
}

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;

    set <int> inds;
    set <pair <int, int>> toRemove;

    for(int i = 0;i<M;i++)
    {
        dp[i] = getInside(1, K[i], K[i], n) - K[i];
        while(toRemove.empty()==false && toRemove.begin()->first<=K[i])
        {
            int j = toRemove.begin()->second;
            toRemove.erase(toRemove.begin());

            remInd(inds, toRemove, j, M, K);
        }

        if(inds.empty()==false) dp[i] = min(dp[i], eval(i, last(inds), K));
        addInd(inds, toRemove, i, M, K);
    }

    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
*/

컴파일 시 표준 에러 (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 getBetter(int, int, int, int*)':
teams.cpp:251:14: warning: division by zero [-Wdiv-by-zero]
  251 |     cout << 1/0 << '\n';
      |             ~^~
teams.cpp:211:33: warning: unused parameter 'M' [-Wunused-parameter]
  211 | int getBetter(int i, int j, int M, int K[])
      |                             ~~~~^

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