oj.uz

답안 #1063383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063383 2024-08-17T17:39:40 Z nishkarsh 팀들 (IOI15_teams) C++14
0 / 100
 4000 ms 151924 KB 
#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;

int fastexp(int b, int e, int mod){
	int ans = 1;
	while(e){
		if(e&1) ans = (1ll*ans*b)%mod;
		b = (1ll*b*b)%mod;
		e >>= 1;
	}
	return ans;
}

const int N = 5e5+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
const int logn = 20;

struct pers_segtree_node{
	int lt,rt,val;
};

int pers_segtree_nodecnt = 0;
pers_segtree_node pers_segtree[N*logn];
int update(int node, int i, int j, int ind){
	int nw_node = ++pers_segtree_nodecnt;
	pers_segtree[nw_node] = pers_segtree[node];
	pers_segtree[nw_node].val++;

	if(i == j) return nw_node;

	int mid = (i+j) / 2;
	if(ind <= mid) pers_segtree[nw_node].lt = update(pers_segtree[node].lt, i, mid, ind);
	else pers_segtree[nw_node].rt = update(pers_segtree[node].rt, mid+1, j, ind);
	return nw_node;
}

struct my_segtree_node{
	int curr, latest, last_exhausted;
};

int my_segtree_nodecnt;
my_segtree_node my_segtree[4*N];

void query(int node, int i, int j, int l, int r, int pers_segtree_node_num, int tim, int &val){
	if(val == 0 || pers_segtree_node_num == 0 || i > r || l > j || i > j || l > r) return;
	if(i >= l && j <= r){
		int left = pers_segtree[pers_segtree_node_num].val - pers_segtree[my_segtree[node].latest].val - my_segtree[node].curr;
		if(val >= left){
			val -= left;
			my_segtree[node].latest = pers_segtree_node_num;
			my_segtree[node].last_exhausted = tim;
			my_segtree[node].curr = 0;
			return;
		}
		else my_segtree[node].curr += val;
	}

	if(i == j) return;

	int mid = (i+j) / 2;

	if(my_segtree[2*node].last_exhausted < my_segtree[node].last_exhausted){
		my_segtree[2*node].last_exhausted = my_segtree[node].last_exhausted;
		my_segtree[2*node].curr = 0;
		my_segtree[2*node].latest = pers_segtree[my_segtree[node].latest].lt;
	}

	query(2*node, i, mid, l, r, pers_segtree[pers_segtree_node_num].lt, tim, val);

	if(my_segtree[2*node+1].last_exhausted < my_segtree[node].last_exhausted){
		my_segtree[2*node+1].last_exhausted = my_segtree[node].last_exhausted;
		my_segtree[2*node+1].curr = 0;
		my_segtree[2*node+1].latest = pers_segtree[my_segtree[node].latest].rt;
	}

	query(2*node+1, mid+1, j, l, r, pers_segtree[pers_segtree_node_num].rt, tim, val);
}

void clear_my_segtree(int node, int i, int j){
	if(my_segtree[node].curr == 0 && my_segtree[node].latest == 0 && my_segtree[node].last_exhausted) return;
	my_segtree[node] = {0,0,0};
	if(i==j) return;
	int mid = (i+j)/2;
	clear_my_segtree(2*node,i,mid);
	clear_my_segtree(2*node + 1,mid+1,j);
}

int times[N];
int n;

void init(int N, int *A, int *B){
	n = N;
	vt<vt<int>> ranges(n+1);
	for(int i = 0; i < n; i++) ranges[A[i]].pb(B[i]);

	for(int i = 1; i <= n; i++){
		times[i] = times[i-1];
		for(int j : ranges[i]) times[i] = update(times[i], 1, N, j);
	}
}

bool can(int M, int *K){
	sort(K,K+M);
	for(int i = 0; i < M; i++){
		int temp_val = K[i];
		query(1,1,n,K[i],n,times[K[i]],i+1,temp_val);
		if(temp_val > 0){
			clear_my_segtree(1,1,n);
			return false;
		}
	}
	clear_my_segtree(1,1,n);
	return true;
}

void solve(){
	int n;
	cin >> n;
	int A[n],B[n];
	for(int i = 0; i < n; i++) cin >> A[i] >> B[i];
	init(n,A,B);
	int q,k;
	cin >> q;
	while(q--){
		cin >> k;
		int temp[k];
		for(int i = 0; i < k; i++) cin >> temp[i];
		cout << can(k,temp) << "\n";
	}
}

// int main()
// {
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(NULL);

// 	int t = 1;
// 	// cin >> t;
// 	while(t--){
// 		solve();
// 	}

// 	return 0;
// }

Compilation message

teams.cpp: In function 'int fastexp(int, int, int)':
teams.cpp:10:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 |   if(e&1) ans = (1ll*ans*b)%mod;
      |                 ~~~~~~~~~~~^~~~
teams.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |   b = (1ll*b*b)%mod;
      |       ~~~~~~~~~^~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:96:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   96 | void init(int N, int *A, int *B){
      |           ~~~~^
teams.cpp:17:11: note: shadowed declaration is here
   17 | const int N = 5e5+1;
      |           ^
teams.cpp: In function 'void solve()':
teams.cpp:122:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  122 |  int n;
      |      ^
teams.cpp:94:5: note: shadowed declaration is here
   94 | int n;
      |     ^

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 520 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 27472 KB Output is correct
2 Correct 42 ms 28408 KB Output is correct
3 Correct 38 ms 28204 KB Output is correct
4 Correct 43 ms 28512 KB Output is correct
5 Correct 20 ms 26028 KB Output is correct
6 Correct 22 ms 26720 KB Output is correct
7 Correct 18 ms 26676 KB Output is correct
8 Correct 18 ms 26724 KB Output is correct
9 Incorrect 18 ms 25560 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 27944 KB Output is correct
2 Correct 75 ms 28204 KB Output is correct
3 Execution timed out 4035 ms 28656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 511 ms 150720 KB Output is correct
2 Correct 637 ms 151924 KB Output is correct
3 Execution timed out 4035 ms 151300 KB Time limit exceeded
4 Halted 0 ms 0 KB -