oj.uz

Submission #68673

# Submission time Handle Problem Language Result Execution time Memory
68673 2018-08-17T23:20:01 Z FLDutchman Teams (IOI15_teams) C++14
0 / 100
 1066 ms 186200 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

struct segtree{
	vvi t;
	segtree(int n){
		t.resize(4*n);
	}

	void build(vi &arr, int lb, int rb, int n){
		if(rb-lb == 1) {
			t[n].pb(arr[lb]);
			return;
		}
		int mb = (lb+rb)/2;
		build(arr, lb, mb, n<<1);
		build(arr, mb, rb, n<<1|1);
		sort(&arr[lb], &arr[rb]);
		FOR(i, lb, rb) t[n].pb(arr[i]);
	}

	int qu(int l, int r, int c, int lb, int rb, int n){
		if(l == r) return 0;
		if(n!=0){
			//cout<<n<<endl;
			//cout << l << " " << r << endl;
		}
		if(l <= lb and rb <= r) return upper_bound(t[n].begin(), t[n].end(), c) - t[n].begin();
		int mb = (lb+rb)/2;
		int s = 0;
		if(l < mb) s += qu(l, r, c, lb, mb, n<<1);
		if(r > mb) s += qu(l, r, c, mb, rb, n<<1|1);
		return s;
	}
};

segtree t(0);
vii a, pre;
vi arr, prefix;
vi A, B;
int N;

void init(INT n, INT x[], INT y[]) {
	N = n;
	FOR(i, 0, N) A.pb(x[i]), B.pb(y[i]);
	t = segtree(N);
	a.resize(N);
	FOR(i, 0, N) a[i] = {B[i], A[i]};
	sort(a.begin(), a.end());
	arr.resize(N);
	FOR(i, 0, N) arr[i] = a[i].snd;
	t.build(arr, 0, N, 1);
	FOR(i, 0, N) pre.pb({A[i], -1});
	FOR(i, 0, N) pre.pb({B[i], 1});
	sort(pre.begin(), pre.end());
	prefix.resize(2*N, 0);
	FOR(i, 1, 2*N) prefix[i] = prefix[i-1] - pre[i-1].snd;
}

INT can(INT M, INT K[]) {
	int T = upper_bound(pre.begin(), pre.end(), make_pair(K[0], 0)) - pre.begin();
	
	int active = prefix[T], tbc = 0;
	FOR(i, 0, M-1){
		//cout << active << " " << tbc << endl;
		if(active < K[i]) return 0;
		active -= K[i];
		tbc += K[i];
		if(K[i] == K[i+1]) continue; 
		int nT = upper_bound(pre.begin(), pre.end(), make_pair(K[i+1], 0)) - pre.begin();
		int l = lower_bound(a.begin(), a.end(), make_pair(K[i], 0)) - a.begin();
		int r = lower_bound(a.begin(), a.end(), make_pair(K[i+1], 0)) - a.begin();
		tbc -= t.qu(l, r, K[i], 0, N, 1);
		active = prefix[nT] - tbc;
	}
	if(active < K[M-1]) return 0;
	return 1;
}

Compilation message

teams.cpp: In member function 'int segtree::qu(int, int, int, int, int, int)':
teams.cpp:41:75: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   if(l <= lb and rb <= r) return upper_bound(t[n].begin(), t[n].end(), c) - t[n].begin();
                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp: In function 'INT can(INT, INT*)':
teams.cpp:74:66: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
  int T = upper_bound(pre.begin(), pre.end(), make_pair(K[0], 0)) - pre.begin();
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:83:70: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int nT = upper_bound(pre.begin(), pre.end(), make_pair(K[i+1], 0)) - pre.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:84:63: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int l = lower_bound(a.begin(), a.end(), make_pair(K[i], 0)) - a.begin();
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:85:65: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int r = lower_bound(a.begin(), a.end(), make_pair(K[i+1], 0)) - a.begin();
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Incorrect 2 ms 764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 29672 KB Output is correct
2 Correct 171 ms 30740 KB Output is correct
3 Correct 173 ms 32012 KB Output is correct
4 Correct 164 ms 33744 KB Output is correct
5 Incorrect 124 ms 34056 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 35724 KB Output is correct
2 Correct 167 ms 37284 KB Output is correct
3 Correct 217 ms 42080 KB Output is correct
4 Correct 161 ms 42080 KB Output is correct
5 Incorrect 109 ms 42080 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 158712 KB Output is correct
2 Correct 974 ms 166144 KB Output is correct
3 Correct 1066 ms 180044 KB Output is correct
4 Correct 992 ms 182272 KB Output is correct
5 Incorrect 599 ms 186200 KB Output isn't correct
6 Halted 0 ms 0 KB -