oj.uz

Submission #706490

# Submission time Handle Problem Language Result Execution time Memory
706490 2023-03-06T17:57:19 Z skyvn97 Teams (IOI15_teams) C++14
77 / 100
 2015 ms 386408 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 39372 KB Output is correct
2 Correct 39 ms 39372 KB Output is correct
3 Correct 40 ms 39500 KB Output is correct
4 Correct 40 ms 39500 KB Output is correct
5 Correct 39 ms 39536 KB Output is correct
6 Correct 39 ms 39500 KB Output is correct
7 Correct 46 ms 39548 KB Output is correct
8 Correct 44 ms 39588 KB Output is correct
9 Correct 41 ms 39468 KB Output is correct
10 Correct 43 ms 39588 KB Output is correct
11 Correct 39 ms 39500 KB Output is correct
12 Correct 41 ms 39500 KB Output is correct
13 Correct 43 ms 39528 KB Output is correct
14 Correct 43 ms 39480 KB Output is correct
15 Correct 40 ms 39516 KB Output is correct
16 Correct 39 ms 39504 KB Output is correct
17 Correct 39 ms 39500 KB Output is correct
18 Correct 40 ms 39452 KB Output is correct
19 Correct 41 ms 39484 KB Output is correct
20 Correct 40 ms 39420 KB Output is correct
21 Correct 40 ms 39500 KB Output is correct
22 Correct 40 ms 39464 KB Output is correct
23 Correct 40 ms 39420 KB Output is correct
24 Correct 40 ms 39452 KB Output is correct
25 Correct 40 ms 39496 KB Output is correct
26 Correct 40 ms 39500 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 104860 KB Output is correct
2 Correct 134 ms 104652 KB Output is correct
3 Correct 137 ms 104652 KB Output is correct
4 Correct 133 ms 105224 KB Output is correct
5 Correct 109 ms 104292 KB Output is correct
6 Correct 106 ms 104312 KB Output is correct
7 Correct 108 ms 104324 KB Output is correct
8 Correct 104 ms 104316 KB Output is correct
9 Correct 110 ms 104856 KB Output is correct
10 Correct 99 ms 104268 KB Output is correct
11 Correct 103 ms 104268 KB Output is correct
12 Correct 105 ms 104392 KB Output is correct
13 Correct 112 ms 104560 KB Output is correct
14 Correct 119 ms 104628 KB Output is correct
15 Correct 132 ms 104568 KB Output is correct
16 Correct 131 ms 104596 KB Output is correct
17 Correct 109 ms 104652 KB Output is correct
18 Correct 116 ms 104784 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 105496 KB Output is correct
2 Correct 156 ms 105404 KB Output is correct
3 Correct 727 ms 114428 KB Output is correct
4 Correct 135 ms 105232 KB Output is correct
5 Correct 688 ms 110744 KB Output is correct
6 Correct 619 ms 109844 KB Output is correct
7 Correct 128 ms 105036 KB Output is correct
8 Correct 500 ms 108708 KB Output is correct
9 Correct 105 ms 104640 KB Output is correct
10 Correct 104 ms 104660 KB Output is correct
11 Correct 135 ms 105264 KB Output is correct
12 Correct 629 ms 110800 KB Output is correct
13 Correct 758 ms 112340 KB Output is correct
14 Correct 793 ms 113480 KB Output is correct
15 Correct 539 ms 109416 KB Output is correct
16 Correct 530 ms 109240 KB Output is correct
17 Correct 443 ms 108876 KB Output is correct
18 Correct 379 ms 108108 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 367264 KB Output is correct
2 Correct 643 ms 367928 KB Output is correct
3 Correct 1914 ms 386408 KB Output is correct
4 Correct 604 ms 367432 KB Output is correct
5 Correct 1593 ms 376640 KB Output is correct
6 Correct 1424 ms 374960 KB Output is correct
7 Correct 439 ms 365184 KB Output is correct
8 Correct 1277 ms 373032 KB Output is correct
9 Correct 380 ms 365792 KB Output is correct
10 Correct 365 ms 364236 KB Output is correct
11 Correct 659 ms 368044 KB Output is correct
12 Correct 1586 ms 379012 KB Output is correct
13 Correct 1800 ms 382064 KB Output is correct
14 Correct 2015 ms 384836 KB Output is correct
15 Correct 1330 ms 375828 KB Output is correct
16 Incorrect 1417 ms 376508 KB Output isn't correct
17 Halted 0 ms 0 KB -