oj.uz

Submission #204319

# Submission time Handle Problem Language Result Execution time Memory
204319 2020-02-25T12:03:30 Z Segtree Teams (IOI15_teams) C++14
77 / 100
 4000 ms 162748 KB 
#include"teams.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")

#define up(x,y) upper_bound(all(x),y)
#define NS (1<<19)
vector<P> v;
ll dat[NS*2],laste[2*NS],lastd[2*NS],correctA;
vector<ll> as[NS*2];
int used[NS*100],tot;
void add(int K){
	correctA=K;
}
ll eval(ll k,bool ex){
	if(k==0)return 0;
	if(ex)used[tot++]=k;
	if(k<NS){
		chmax(lastd[k*2],lastd[k]); if(ex)used[tot++]=k*2;
		chmax(lastd[k*2+1],lastd[k]); if(ex)used[tot++]=k*2+1;
	}
	if(lastd[k]==-1e17){
		if(laste[k]!=correctA){
			dat[k]+=up(as[k],correctA)-up(as[k],laste[k]);
		}
	}
	else{
		if(lastd[k]!=correctA){
			dat[k]=up(as[k],correctA)-up(as[k],lastd[k]);
		}
		else dat[k]=0;
	}
	laste[k]=correctA;
	lastd[k]=-1e17;
	return dat[k];
}
void erase(ll l,ll r){
	l+=NS,r+=NS+1;
	for(ll d=20;~d;d--){
		eval(l>>d,1);
		eval(r>>d,1);
	}
	for(ll a=l,b=r;a<b;a>>=1,b>>=1){
		if(a&1){chmax(lastd[a],correctA);a++;}
		if(b&1){b--;chmax(lastd[b],correctA);}
	}
	for(ll a=l,b=r;a+b;a>>=1,b>>=1){
		dat[a/2]=eval(a,1)+eval(a^1,1);
		dat[b/2]=eval(b,1)+eval(b^1,1);
	}
}

void init(int N,int A[],int B[]){
	rep(i,N)v.emplace_back(make_pair(B[i],A[i]));
	sort(v.begin(),v.end());
	rep(i,NS){
		if(i<N)as[i+NS].emplace_back(v[i].second);
	}
	for(int i=NS-1;i>0;i--){
		for(auto t:as[i*2])as[i].emplace_back(t);
		for(auto t:as[i*2+1])as[i].emplace_back(t);
		sort(as[i].begin(),as[i].end());
	}
}

int can(int M,int K[]){
	tot=0;
	correctA=0;
	sort(K,K+M);
	bool ans=1;
	rep(i,M){
		add(K[i]);
		ll l,r,mid;
		l=-1,r=v.size();
		while(l<r-1){
			mid=(l+r)>>1;
			(v[mid].first<K[i]?l:r)=mid;
		}
		erase(0,l);
		if(eval(1,1)<K[i]){
			ans=0;
			break;
		}
		ll k=1,rui=0;
		while(k<NS){
			ll ev=eval(k*2,1);
			if(rui+ev>=K[i]){
				k=k*2;
			}
			else{
				rui+=ev;
				k=k*2+1;
			}
		}
		erase(0,k-NS);
	}
	rep(i,tot)dat[used[i]]=0,laste[used[i]]=lastd[used[i]]=-1e17;
	return ans;
}
/*
int main(){
	int n,a[110],b[110];
	cin>>n;
	rep(i,n)cin>>a[i]>>b[i];
	init(n,a,b);
	while(1){
		int m,k[110];
		cin>>m;
		rep(i,m)cin>>k[i];
		cout<<(can(m,k)?"YES":"NO")<<endl;
	}
}*/

Compilation message

teams.cpp:16:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
teams.cpp:17:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
teams.cpp:18:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
 
teams.cpp: In function 'll eval(ll, bool)':
teams.cpp:31:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if(ex)used[tot++]=k;
                    ^
teams.cpp:33:50: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   chmax(lastd[k*2],lastd[k]); if(ex)used[tot++]=k*2;
                                                 ~^~
teams.cpp:34:54: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   chmax(lastd[k*2+1],lastd[k]); if(ex)used[tot++]=k*2+1;
                                                   ~~~^~
teams.cpp:36:12: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
  if(lastd[k]==-1e17){
     ~~~~~~~^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25080 KB Output is correct
2 Correct 23 ms 25080 KB Output is correct
3 Correct 27 ms 25208 KB Output is correct
4 Correct 25 ms 25208 KB Output is correct
5 Correct 24 ms 25208 KB Output is correct
6 Correct 24 ms 25208 KB Output is correct
7 Correct 33 ms 25208 KB Output is correct
8 Correct 30 ms 25208 KB Output is correct
9 Correct 25 ms 25212 KB Output is correct
10 Correct 28 ms 25208 KB Output is correct
11 Correct 25 ms 25208 KB Output is correct
12 Correct 43 ms 25340 KB Output is correct
13 Correct 34 ms 25208 KB Output is correct
14 Correct 30 ms 25208 KB Output is correct
15 Correct 26 ms 25208 KB Output is correct
16 Correct 25 ms 25208 KB Output is correct
17 Correct 31 ms 25124 KB Output is correct
18 Correct 29 ms 25208 KB Output is correct
19 Correct 28 ms 25208 KB Output is correct
20 Correct 27 ms 25208 KB Output is correct
21 Correct 27 ms 25208 KB Output is correct
22 Correct 27 ms 25208 KB Output is correct
23 Correct 26 ms 25208 KB Output is correct
24 Correct 25 ms 25080 KB Output is correct
25 Correct 25 ms 25080 KB Output is correct
26 Correct 26 ms 25208 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 48488 KB Output is correct
2 Correct 138 ms 48360 KB Output is correct
3 Correct 138 ms 48336 KB Output is correct
4 Correct 140 ms 48500 KB Output is correct
5 Correct 108 ms 54248 KB Output is correct
6 Correct 96 ms 53224 KB Output is correct
7 Correct 91 ms 48208 KB Output is correct
8 Correct 96 ms 48232 KB Output is correct
9 Correct 327 ms 149864 KB Output is correct
10 Correct 222 ms 105704 KB Output is correct
11 Correct 110 ms 58728 KB Output is correct
12 Correct 90 ms 52712 KB Output is correct
13 Correct 102 ms 49512 KB Output is correct
14 Correct 98 ms 48232 KB Output is correct
15 Correct 131 ms 48616 KB Output is correct
16 Correct 138 ms 48360 KB Output is correct
17 Correct 95 ms 49512 KB Output is correct
18 Correct 94 ms 49640 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 48360 KB Output is correct
2 Correct 155 ms 49004 KB Output is correct
3 Correct 1727 ms 55232 KB Output is correct
4 Correct 138 ms 48232 KB Output is correct
5 Correct 1519 ms 54264 KB Output is correct
6 Correct 1365 ms 54516 KB Output is correct
7 Correct 102 ms 48232 KB Output is correct
8 Correct 1042 ms 54268 KB Output is correct
9 Correct 314 ms 149784 KB Output is correct
10 Correct 672 ms 105960 KB Output is correct
11 Correct 796 ms 58984 KB Output is correct
12 Correct 1152 ms 53740 KB Output is correct
13 Correct 1679 ms 53048 KB Output is correct
14 Correct 1844 ms 53896 KB Output is correct
15 Correct 809 ms 49212 KB Output is correct
16 Correct 799 ms 49132 KB Output is correct
17 Correct 803 ms 50412 KB Output is correct
18 Correct 742 ms 50408 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 139380 KB Output is correct
2 Correct 709 ms 140192 KB Output is correct
3 Execution timed out 4082 ms 162748 KB Time limit exceeded
4 Halted 0 ms 0 KB -