Submission #139225

#	Time	Username	Problem	Language	Result	Execution time	Memory
139225		Lawliet	Meetings (IOI18_meetings)	C++14	0 / 100	40 ms	2464 KiB

meetings

#include <bits/stdc++.h>

#define MAX 100010

using namespace std;
typedef long long int lli;

class SegmentTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void merge(int node, int idLeft, int idRight)
		{
			mx[ node ] = max(mx[ idLeft ] , mx[ idRight ]);

			blockLeft[ node ] = blockLeft[ idLeft ];
			blockRight[ node ] = blockRight[ idRight ];

			if(mx[ idLeft ] == 1) blockLeft[ node ] += blockLeft[ idRight ];
			if(mx[ idRight ] == 1) blockRight[ node ] += blockRight[ idLeft ];

			block[ node ] = max(block[ idLeft ] , block[ idRight ]);
			block[ node ] = max(block[ node ] , blockRight[ idLeft ] + blockLeft[ idRight ]);
		}

		void build(int node, int l, int r, int* v)
		{
			N = max(N , r);

			if(l == r)
			{
				int aux = 0;

				if(v[l] == 1) aux = 1;

				mx[ node ] = v[ l ];
				block[ node ] = aux;
				blockLeft[ node ] = aux;
				blockRight[ node ] = aux;

				return;
			}

			int m = (l + r)/2;

			build(getLeft(node) , l , m , v);
			build(getRight(node) , m + 1 , r , v);

			merge(node , getLeft(node) , getRight(node));
		}

		void query(int node, int l, int r, int i, int j)
		{
			if(j < l || r < i) return;

			if(i <= l && r <= j) 
			{
				merge(1 , 0 , node);

				mx[0] = mx[1];
				block[0] = block[1];
				blockLeft[0] = blockLeft[1];
				blockRight[0] = blockRight[1];

				return;
			}

			int m = (l + r)/2;

			query(getLeft(node) , l , m , i , j);
			query(getRight(node) , m + 1 , r , i , j);
		}

		int query(int l, int r)
		{
			mx[0] = mx[1] = -1;
			block[0] = block[1] = 0;
			blockLeft[0] = blockLeft[1] = 0;
			blockRight[0] = blockRight[1] = 0;

			query(2 , 1 , N , l , r);

			return block[ 0 ];
		}

		SegmentTree() : N( 0 ) {}

	private:

		int N;

		int mx[4*MAX];
		int block[4*MAX];
		int blockLeft[4*MAX];
		int blockRight[4*MAX];
};

int N, Q;

int v[MAX];

vector<lli> ans;

SegmentTree SEG;

vector<long long int> minimum_costs(vector<int> H, vector<int> l, vector<int> r)
{
	N = H.size(); Q = l.size();

	for(int g = 1 ; g <= N ; g++)
		v[ g ] = H[ g - 1 ];

	SEG.build(1 , 1 , N , v);

	for(int g = 0 ; g < Q ; g++)
	{
		int L = l[g] + 1;
		int R = r[g] + 1;

		int blockOne = SEG.query(L , R);

		ans.push_back( blockOne*1 + (R - L + 1 - blockOne)*2 );
	}

	return ans;
}

/*int main()
{
	int nn, qq;

	scanf("%d %d",&nn,&qq);

	vector<int> hh(nn);
	vector<int> ll(qq), rr(qq);

	for(int g = 0 ; g < nn ; g++)
		scanf("%d",&hh[g]);

	for(int g = 0 ; g < qq ; g++)
		scanf("%d %d",&ll[g],&rr[g]);

	vector<lli> aux = minimum_costs(hh , ll , rr);

	for(int g = 0 ; g < qq ; g++)
		printf("%lld\n",aux[g]);
}*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40