Submission #706490

#	Time	Username	Problem	Language	Result	Execution time	Memory
706490		skyvn97	Teams (IOI15_teams)	C++14	77 / 100	2015 ms	386408 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define MAX   500500
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
using namespace std;
class SegmentTree {
    private:
    struct Node {
        int cnt;
        Node *left,*right;
        Node() {
            cnt=0;
            left=right=NULL;
        }
        Node(Node *p) {
            cnt=p->cnt;
            left=p->left;
            right=p->right;
        }
    };
    Node *root;
    int n;
    int get(Node *p,int l,int r,int u,int v) const {
        if (l>v || r<u || l>r || v<u) return (0);
        if (u<=l && r<=v) return (p->cnt);
        int m=(l+r)>>1;
        int L=get(p->left,l,m,u,v);
        int R=get(p->right,m+1,r,u,v);
        return (L+R);
    }
    void build(Node *&p,int l,int r) {
        if (l>r) return;
        p=new Node();
        if (l==r) return;
        int m=(l+r)>>1;
        build(p->left,l,m);
        build(p->right,m+1,r);
    }
    public:
    SegmentTree() {
        n=0;
        root=NULL;
    }
    SegmentTree(int n) {
        this->n=n;
        build(root,1,n);
    }
    void update(int x) {
        assert(1<=x && x<=n);
        root=new Node(root);
        Node *p=root;
        int l=1;
        int r=n;
        while (true) {
            p->cnt++;
            if (l==r) return;
            int m=(l+r)>>1;
            if (x>m) {
                l=m+1;
                p->right=new Node(p->right);
                p=p->right;
            } else {
                r=m;
                p->left=new Node(p->left);
                p=p->left;
            }
        }
    }
    int get(int l,int r) const {
        assert(1<=l && r<=n);
        return (get(root,1,n,l,r));
    }
};
int n,cntTime;
pair<int,int> a[MAX];
SegmentTree myit[MAX+7];
int randint(int l,int r) {
    assert(l<=r);
    return (l+rand()%(r-l+1));
}
void init(int N, int A[], int B[]) {
    n=N;
    REP(i,n) {
        /*int L=randint(1,n);
        int R=randint(1,n);
        if (L>R) swap(L,R);*/
        a[i+1]=make_pair(A[i],B[i]);
    }
    sort(a+1,a+n+1);
    myit[0]=SegmentTree(MAX);
    int id=1;
    FOR(i,1,MAX) {
        myit[i]=myit[i-1];
        while (id<=n && a[id].fi<=i) {
            myit[i].update(a[id].se);
            id++;
        }
    }
    /*srand(time(NULL));
    int a=0;
    REP(love,1000000) {
        int L=randint(1,MAX);
        int minR=randint(1,MAX);
        int maxR=randint(1,MAX);
        if (minR>maxR) swap(minR,maxR);
        //cerr<<L<<" "<<minR<<" "<<maxR<<endl;
        a^=myit[L].get(minR,maxR);
    }
    cerr<<a<<endl;
    fprintf(stderr,"Done\n");*/
}
int countPair(int l,int minR,int maxR) {
    if (l<1) return (0);
    if (minR<1) minR=1;
    if (maxR>MAX) maxR=MAX;
    if (minR>maxR) return (0);
    /*int res=0;
    FOR(i,1,n) if (a[i].fi<=l && minR<=a[i].se && a[i].se<=maxR) res++;
    return (res);*/
    return (myit[l].get(minR,maxR));
}
int countPair(int minL,int maxL,int minR,int maxR) {
    if (minL>maxL || minR>maxR) return (0);
    return (countPair(maxL,minR,maxR)-countPair(minL-1,minR,maxR));
}
int can(int M, int K[]) {
    long long sum=0;
    REP(i,M) sum+=K[i];
    if (sum>n) return (0);
    map<int,int> mp;
    REP(i,M) mp[K[i]]+=K[i];
    vector<pair<int,int> > v(ALL(mp));
    int prevUsed=0;
    REP(i,v.size()) {
        int cur=v[i].fi;
        int req=v[i].se;
        fprintf(stderr,"At value %d req %d\n",cur,req);
        int next=i+1<(int)v.size()?v[i+1].fi:MAX;
        int prev=i>0?v[i-1].fi:-1;
        int oldSmall=countPair(1,prev,cur,next-1);
        int oldBig=countPair(1,prev,next,MAX);
        int newSmall=countPair(prev+1,cur,cur,next-1);
        int newBig=countPair(prev+1,cur,next,MAX);
        fprintf(stderr,"old: %d | %d\n",oldSmall,oldBig);
        fprintf(stderr,"new: %d | %d\n",newSmall,newBig);
        assert(oldSmall+oldBig>=prevUsed);
        if (oldSmall<prevUsed) {
            oldBig-=prevUsed-oldSmall;
            prevUsed-=oldSmall;
            oldSmall=0;
        } else {
            oldSmall-=prevUsed;
            prevUsed=0;
        }
        int numSmall=oldSmall+newSmall;
        int numBig=oldBig+newBig;
        if (numSmall+numBig<req) return (0);
        prevUsed+=numSmall<req?req-numSmall:0;
        fprintf(stderr,"prevUsed %d\n",prevUsed);
    }
    return (1);
}

Compilation message (stderr)

teams.cpp: In constructor 'SegmentTree::SegmentTree(int)':
teams.cpp:49:21: warning: declaration of 'n' shadows a member of 'SegmentTree' [-Wshadow]
   49 |     SegmentTree(int n) {
      |                 ~~~~^
teams.cpp:27:9: note: shadowed declaration is here
   27 |     int n;
      |         ^
teams.cpp: In constructor 'SegmentTree::SegmentTree(int)':
teams.cpp:49:21: warning: declaration of 'n' shadows a member of 'SegmentTree' [-Wshadow]
   49 |     SegmentTree(int n) {
      |                 ~~~~^
teams.cpp:27:9: note: shadowed declaration is here
   27 |     int n;
      |         ^
teams.cpp: In constructor 'SegmentTree::SegmentTree(int)':
teams.cpp:49:21: warning: declaration of 'n' shadows a member of 'SegmentTree' [-Wshadow]
   49 |     SegmentTree(int n) {
      |                 ~~~~^
teams.cpp:27:9: note: shadowed declaration is here
   27 |     int n;
      |         ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:139:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
    5 | #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
      |                                  ~~~
......
  139 |     REP(i,v.size()) {
teams.cpp:5:35: note: in definition of macro 'REP'
    5 | #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
      |                                   ^

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