oj.uz

답안 #197913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197913 2020-01-24T07:56:14 Z mhy908 팀들 (IOI15_teams) C++14
100 / 100
 3396 ms 337680 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
struct NODE{
    int val;
    NODE *l, *r;
    NODE(int _val, NODE *_l=nullptr, NODE *_r=nullptr): val(_val), l(_l), r(_r) {}
    NODE* in(int st, int fin, int k){
        if(k<st||k>fin)return this;
        if(st==fin)return new NODE(this->val+1, l, r);
        return new NODE(this->val+1, l->in(st, (st+fin)/2, k), r->in((st+fin)/2+1, fin, k));
    }
    int query(int st, int fin, int ll, int rr){
        if(rr<st||ll>fin)return 0;
        if(ll<=st&&rr>=fin)return this->val;
        return l->query(st, (st+fin)/2, ll, rr)+r->query((st+fin)/2+1, fin, ll, rr);
    }
};
NODE *root[500010];
int pos[500010], n;

void init(int N, int A[], int B[]){
    n=N;
    vector<pii> vc;
    for(int i=0; i<n; i++){
        vc.pb(mp(A[i], B[i]));
    }
    sortvec(vc);
    root[0]=new NODE(0);
    root[0]->l=root[0]->r=root[0];
    for(int i=1; i<=n; i++){
        root[i]=root[i-1]->in(1, n, vc[i-1].S);
        pos[vc[i-1].F]=i;
    }
    for(int i=1; i<=n; i++){
        if(!pos[i])pos[i]=pos[i-1];
    }
}

int can(int m, int k[]){
    sort(k, k+m);
    vector<int> vc, ch;
    for(int i=0; i<m; i++)vc.pb(k[i]);
    compress(vc);
    ch.resize(vc.size());
    int point=0, point2=0;
    for(int i=0; i<m; i++){
        while(vc[point]<k[i])point++;
        if(i&&k[i]!=k[i-1])point2=point;
        int temp=k[i];
        while(temp&&point2<vc.size()){
            int ans;
            if(point2==vc.size()-1)ans=root[pos[k[i]]]->query(1, n, vc[point2], n)-ch[point2];
            else ans=root[pos[k[i]]]->query(1, n, vc[point2], vc[point2+1]-1)-ch[point2];
            ch[point2]+=min(ans, temp);
            temp-=min(ans, temp);
            if(!temp)break;
            point2++;
        }
        if(temp)return 0;
    }
    return 1;
}

//thx a lot to short impl. of PST to gnoor

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(temp&&point2<vc.size()){
                     ~~~~~~^~~~~~~~~~
teams.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(point2==vc.size()-1)ans=root[pos[k[i]]]->query(1, n, vc[point2], n)-ch[point2];
                ~~~~~~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 0 ms 380 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 1 ms 376 KB Output is correct
18 Correct 1 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 0 ms 248 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 3 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 59728 KB Output is correct
2 Correct 193 ms 59644 KB Output is correct
3 Correct 214 ms 59560 KB Output is correct
4 Correct 170 ms 60476 KB Output is correct
5 Correct 116 ms 59216 KB Output is correct
6 Correct 118 ms 59244 KB Output is correct
7 Correct 112 ms 59284 KB Output is correct
8 Correct 116 ms 59244 KB Output is correct
9 Correct 112 ms 57196 KB Output is correct
10 Correct 110 ms 56960 KB Output is correct
11 Correct 113 ms 60012 KB Output is correct
12 Correct 110 ms 57000 KB Output is correct
13 Correct 123 ms 60256 KB Output is correct
14 Correct 123 ms 58096 KB Output is correct
15 Correct 154 ms 59600 KB Output is correct
16 Correct 165 ms 59528 KB Output is correct
17 Correct 120 ms 60396 KB Output is correct
18 Correct 118 ms 60552 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 59788 KB Output is correct
2 Correct 211 ms 59864 KB Output is correct
3 Correct 312 ms 62932 KB Output is correct
4 Correct 174 ms 60484 KB Output is correct
5 Correct 155 ms 59472 KB Output is correct
6 Correct 147 ms 59500 KB Output is correct
7 Correct 137 ms 59516 KB Output is correct
8 Correct 147 ms 59516 KB Output is correct
9 Correct 115 ms 57172 KB Output is correct
10 Correct 122 ms 56996 KB Output is correct
11 Correct 165 ms 60120 KB Output is correct
12 Correct 1052 ms 57332 KB Output is correct
13 Correct 394 ms 60648 KB Output is correct
14 Correct 342 ms 61244 KB Output is correct
15 Correct 189 ms 59784 KB Output is correct
16 Correct 188 ms 59884 KB Output is correct
17 Correct 147 ms 60684 KB Output is correct
18 Correct 147 ms 60780 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1144 ms 333264 KB Output is correct
2 Correct 1176 ms 333352 KB Output is correct
3 Correct 1481 ms 337680 KB Output is correct
4 Correct 1036 ms 333476 KB Output is correct
5 Correct 726 ms 330464 KB Output is correct
6 Correct 718 ms 330464 KB Output is correct
7 Correct 672 ms 330488 KB Output is correct
8 Correct 715 ms 330536 KB Output is correct
9 Correct 610 ms 316052 KB Output is correct
10 Correct 639 ms 329832 KB Output is correct
11 Correct 2197 ms 330444 KB Output is correct
12 Correct 3396 ms 330976 KB Output is correct
13 Correct 1647 ms 332392 KB Output is correct
14 Correct 1500 ms 332280 KB Output is correct
15 Correct 956 ms 333272 KB Output is correct
16 Correct 971 ms 333384 KB Output is correct
17 Correct 705 ms 333260 KB Output is correct
18 Correct 705 ms 333356 KB Output is correct