oj.uz

Submission #892926

# Submission time Handle Problem Language Result Execution time Memory
892926 2023-12-26T07:43:30 Z thunopro Food Court (JOI21_foodcourt) C++14
14 / 100
 204 ms 148464 KB 
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009 
#define ll long long
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef vector<ll> vl ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ;  

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;} 
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow(a,n/2) ;
	if ( n % 2 ) return (1ll*res*res%mod*a%mod) ; 
	else return 1ll*res*res%mod ; 
}

int n , m , nq ; 

struct shape {
	int op , l , r , c , k ; 
	int pos ; 
	ll b ; 
} q [maxn] ;

deque <pll> deq [maxn] ; 
void sub1 () 
{
	for ( int run = 1 ; run <= nq ; run ++ ) 
	{
		int op = q [run].op ; 
		if ( op <= 2 ) 
		{
			int l = q [run].l , r = q [run].r , c = q [run].c , k = q [run].k ; 
			if ( op == 1 ) 
			{
				for ( int i = l ; i <= r ; i ++ ) 
				{
					if ( deq[i].empty() || deq[i].back().fi != c ) deq[i] . push_back ({c,k}) ; 
					else deq[i].back().se += k ; 
				}
			}
			else 
			{
				for ( int i = l ; i <= r ; i ++ ) 
				{
					int remain = k ; 
					while ( deq[i].size () ) 
					{
						if ( deq[i].front().se <= remain ) remain -= deq[i].front().se , deq[i].pop_front () ; 
						else 
						{
							deq[i].front().se -= remain ; 
							break ; 
						}
					}
				}
			}
		}
		else 
		{
			int pos = q[run].pos ; 
			ll b = q [run].b ; 
			deque <pll> New = deq [pos] ; 
			ll sum = 0 ; 
			
			int res = 0 ; 
			
			while ( !New.empty() ) 
			{
				if ( sum + New.front().se >= b )
				{
					res = New.front().fi ; 
					break ; 
				}
				sum += New.front().se ; 
				New.pop_front() ; 
			}
			
			cout << res << "\n" ; 
		}
	}
}

bool check_sub2 () 
{
	if ( max (n,nq) > 65000 ) return false ; 
	for ( int i = 1 ; i <= nq ; i ++ ) 
	{
		if ( q[i].op == 1 ) 
		{
			if ( q[i].r - q [i].l > 10 ) return false ;
			if ( q[i].k != 1 ) return false ; 
		 } 
	}
	return true ; 
}

const int N = 2.5 * 1e5 ; 
ll T[maxn*4] , lazy [maxn*4] ; 

void down_leave_sub2 ( int id ) 
{
	ll &t = lazy [id] ; 
	T [left] += t , T [right] += t ; 
	lazy [left] += t , lazy [right] += t ; 
	t = 0 ; 
}
void update_leave_sub2 ( int id , int l , int r , int u , int v , int k ) 
{
	if ( l > v || r < u ) return ; 
	if ( u <= l && r <= v ) 
	{
		T [id] += k ; 
		lazy [id] += k ; 
		if ( k == - 1 ) 
		{
			T [id] = lazy [id] = 0 ; 
		}
		return ; 
	}
	int mid = (l+r)/2 ; 
	down_leave_sub2 (id) ; 
	update_leave_sub2 (left,l,mid,u,v,k) ; 
	update_leave_sub2 (right,mid+1,r,u,v,k) ; 
}
ll get_leave_sub2 ( int id , int l , int r , int pos ) 
{
	if ( l > pos || r < pos ) return 0 ; 
	if ( l == r ) return T [id] ; 
	down_leave_sub2 (id) ; 
	int mid = (l+r)/2 ; 
	return get_leave_sub2 (left,l,mid,pos) + get_leave_sub2 (right,mid+1,r,pos) ;
}

void leave_sub2 ( int pos ) 
{
	ll leave = get_leave_sub2 (1,1,N,pos) ; 
	update_leave_sub2 (1,1,N,pos,pos,-1) ; 
	while ( deq[pos].size () ) 
	{
		if ( deq[pos].front().se <= leave ) leave -= deq[pos].front().se , deq[pos].pop_front() ; 
		else
		{
			deq[pos].front().se -= leave ; 
			break ; 
		}
	}
}

void sub2 ()  
{
	for ( int run = 1 ; run <= nq ; run ++ ) 
	{
		if ( q [run].op <= 2 ) 
		{
			int l = q [run].l , r = q [run].r , c = q [run].c , k = q [run].k ; 
			if ( q[run].op == 1 ) 
			{
				for ( int i = l ; i <= r ; i ++ ) 
				{
					leave_sub2 (i) ; 
					if ( deq[i].empty() || deq[i].back().fi != c ) deq[i] . push_back ({c,k}) ; 
					else deq[i].back().se += k ; 
				}
			}
			else
			{
				int l = q[run].l , r = q[run].r , k = q [run].k ; 
				update_leave_sub2 (1,1,N,l,r,k) ; 
			} 
		}
		else 
		{
			int pos = q[run].pos ; ll b = q [run].b ; 
			leave_sub2 (pos) ; 
			deque <pll> New = deq [pos] ; 
			ll sum = 0 ; 
			
			int res = 0 ; 
			
			while ( !New.empty() ) 
			{
				if ( sum + New.front().se >= b )
				{
					res = New.front().fi ; 
					break ; 
				}
				sum += New.front().se ; 
				New.pop_front() ; 
			}
			
			cout << res << "\n" ; 
		}
	}
}

void down_leave_sub3 ( int id ) 
{
	ll &t = lazy [id] ; 
	T [left] += t , T [right] += t ; 
	lazy [left] += t , lazy [right] += t ; 
	t = 0 ; 
}
void update_leave_sub3 ( int id , int l , int r , int u , int v , int k ) 
{
	if ( l > v || r < u ) return ; 
	if ( u <= l && r <= v && T [id]+k >= 0 ) 
	{
		T [id] += k ; 
		lazy [id] += k ; 
		return ; 
	}
	if ( l == r ) 
	{
		T [id] = max (T[id]+k,0ll) ; 
		return ; 
	}
	int mid = (l+r)/2 ; 
	down_leave_sub3 (id) ; 
	update_leave_sub3 (left,l,mid,u,v,k) ; 
	update_leave_sub3 (right,mid+1,r,u,v,k) ; 
	T [id] = min (T[left],T[right]) ; 
}
ll get_leave_sub3 ( int id , int l , int r , int pos ) 
{
	if ( l > pos || r < pos ) return 0 ; 
	if ( l == r ) return T [id] ; 
	int mid = (l+r)/2 ; 
	down_leave_sub3 (id) ; 
	return get_leave_sub3 (left,l,mid,pos) + get_leave_sub3 (right,mid+1,r,pos) ; 
}
void sub3 () 
{
	for ( int run = 1 ; run <= nq ; run ++ ) 
	{
		int l = q [run].l , r = q [run].r , k = q [run].k ; 
		if ( q [run].op == 1 ) 
		{
			update_leave_sub3 (1,1,N,l,r,k) ; 
		}
		else if ( q [run].op == 2 ) 
		{
			update_leave_sub3 (1,1,N,l,r,-k) ;
		}
		else 
		{
			int pos = q [run].pos ; ll b = q [run].b ; 
			if ( get_leave_sub3 (1,1,N,pos) >= b ) cout << 1 << "\n" ; 
			else cout << 0 << "\n" ; 
		}
	}
}
int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 
	cin >> n >> m >> nq ; 
	for ( int i = 1 ; i <= nq ; i ++ ) 
	{
		cin >> q[i].op ; 
		if ( q[i].op == 1 ) 
		{
			cin >> q[i].l >> q[i].r >> q[i].c >> q[i].k ; 
		}
		else if ( q[i].op == 2 ) 
		{
			cin >> q[i].l >> q[i].r >> q [i].k ; 
		}
		else cin >> q[i].pos >> q[i].b ; 
	}

	if ( n <= 2e3 && nq <= 2e3 ) sub1 () ; 
	else if ( check_sub2 () ) sub2 () ; 
	else if ( m == 1 ) sub3 () ; 
}

Compilation message

foodcourt.cpp: In function 'void rf()':
foodcourt.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 136276 KB Output is correct
2 Correct 85 ms 136632 KB Output is correct
3 Correct 94 ms 143284 KB Output is correct
4 Correct 97 ms 146768 KB Output is correct
5 Correct 73 ms 135656 KB Output is correct
6 Correct 69 ms 135764 KB Output is correct
7 Correct 99 ms 148304 KB Output is correct
8 Correct 97 ms 144256 KB Output is correct
9 Correct 87 ms 136528 KB Output is correct
10 Correct 91 ms 143276 KB Output is correct
11 Correct 93 ms 140452 KB Output is correct
12 Correct 90 ms 137060 KB Output is correct
13 Correct 92 ms 136788 KB Output is correct
14 Correct 97 ms 137808 KB Output is correct
15 Correct 90 ms 138576 KB Output is correct
16 Correct 99 ms 137880 KB Output is correct
17 Correct 93 ms 135996 KB Output is correct
18 Correct 88 ms 136352 KB Output is correct
19 Correct 72 ms 135776 KB Output is correct
20 Correct 71 ms 135656 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 136276 KB Output is correct
2 Correct 85 ms 136632 KB Output is correct
3 Correct 94 ms 143284 KB Output is correct
4 Correct 97 ms 146768 KB Output is correct
5 Correct 73 ms 135656 KB Output is correct
6 Correct 69 ms 135764 KB Output is correct
7 Correct 99 ms 148304 KB Output is correct
8 Correct 97 ms 144256 KB Output is correct
9 Correct 87 ms 136528 KB Output is correct
10 Correct 91 ms 143276 KB Output is correct
11 Correct 93 ms 140452 KB Output is correct
12 Correct 90 ms 137060 KB Output is correct
13 Correct 92 ms 136788 KB Output is correct
14 Correct 97 ms 137808 KB Output is correct
15 Correct 90 ms 138576 KB Output is correct
16 Correct 99 ms 137880 KB Output is correct
17 Correct 93 ms 135996 KB Output is correct
18 Correct 88 ms 136352 KB Output is correct
19 Correct 72 ms 135776 KB Output is correct
20 Correct 71 ms 135656 KB Output is correct
21 Correct 91 ms 136564 KB Output is correct
22 Correct 84 ms 136528 KB Output is correct
23 Correct 98 ms 143176 KB Output is correct
24 Correct 103 ms 147080 KB Output is correct
25 Correct 70 ms 135764 KB Output is correct
26 Correct 70 ms 135612 KB Output is correct
27 Correct 96 ms 147792 KB Output is correct
28 Correct 96 ms 144720 KB Output is correct
29 Correct 93 ms 138324 KB Output is correct
30 Correct 94 ms 142928 KB Output is correct
31 Correct 92 ms 140464 KB Output is correct
32 Correct 90 ms 136592 KB Output is correct
33 Correct 93 ms 136568 KB Output is correct
34 Correct 97 ms 138836 KB Output is correct
35 Correct 93 ms 137300 KB Output is correct
36 Correct 96 ms 137704 KB Output is correct
37 Correct 76 ms 135700 KB Output is correct
38 Correct 69 ms 135764 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 148152 KB Output is correct
2 Correct 163 ms 148048 KB Output is correct
3 Correct 178 ms 148052 KB Output is correct
4 Correct 174 ms 148464 KB Output is correct
5 Correct 201 ms 148208 KB Output is correct
6 Correct 200 ms 148048 KB Output is correct
7 Correct 102 ms 144488 KB Output is correct
8 Correct 99 ms 143952 KB Output is correct
9 Correct 144 ms 148052 KB Output is correct
10 Correct 144 ms 148052 KB Output is correct
11 Correct 172 ms 148312 KB Output is correct
12 Correct 144 ms 148052 KB Output is correct
13 Correct 157 ms 148132 KB Output is correct
14 Correct 178 ms 148128 KB Output is correct
15 Correct 191 ms 148136 KB Output is correct
16 Correct 204 ms 148052 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 142076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 136276 KB Output is correct
2 Correct 85 ms 136632 KB Output is correct
3 Correct 94 ms 143284 KB Output is correct
4 Correct 97 ms 146768 KB Output is correct
5 Correct 73 ms 135656 KB Output is correct
6 Correct 69 ms 135764 KB Output is correct
7 Correct 99 ms 148304 KB Output is correct
8 Correct 97 ms 144256 KB Output is correct
9 Correct 87 ms 136528 KB Output is correct
10 Correct 91 ms 143276 KB Output is correct
11 Correct 93 ms 140452 KB Output is correct
12 Correct 90 ms 137060 KB Output is correct
13 Correct 92 ms 136788 KB Output is correct
14 Correct 97 ms 137808 KB Output is correct
15 Correct 90 ms 138576 KB Output is correct
16 Correct 99 ms 137880 KB Output is correct
17 Correct 93 ms 135996 KB Output is correct
18 Correct 88 ms 136352 KB Output is correct
19 Correct 72 ms 135776 KB Output is correct
20 Correct 71 ms 135656 KB Output is correct
21 Correct 154 ms 148152 KB Output is correct
22 Correct 163 ms 148048 KB Output is correct
23 Correct 178 ms 148052 KB Output is correct
24 Correct 174 ms 148464 KB Output is correct
25 Correct 201 ms 148208 KB Output is correct
26 Correct 200 ms 148048 KB Output is correct
27 Correct 102 ms 144488 KB Output is correct
28 Correct 99 ms 143952 KB Output is correct
29 Correct 144 ms 148052 KB Output is correct
30 Correct 144 ms 148052 KB Output is correct
31 Correct 172 ms 148312 KB Output is correct
32 Correct 144 ms 148052 KB Output is correct
33 Correct 157 ms 148132 KB Output is correct
34 Correct 178 ms 148128 KB Output is correct
35 Correct 191 ms 148136 KB Output is correct
36 Correct 204 ms 148052 KB Output is correct
37 Incorrect 87 ms 137848 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 137812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 136276 KB Output is correct
2 Correct 85 ms 136632 KB Output is correct
3 Correct 94 ms 143284 KB Output is correct
4 Correct 97 ms 146768 KB Output is correct
5 Correct 73 ms 135656 KB Output is correct
6 Correct 69 ms 135764 KB Output is correct
7 Correct 99 ms 148304 KB Output is correct
8 Correct 97 ms 144256 KB Output is correct
9 Correct 87 ms 136528 KB Output is correct
10 Correct 91 ms 143276 KB Output is correct
11 Correct 93 ms 140452 KB Output is correct
12 Correct 90 ms 137060 KB Output is correct
13 Correct 92 ms 136788 KB Output is correct
14 Correct 97 ms 137808 KB Output is correct
15 Correct 90 ms 138576 KB Output is correct
16 Correct 99 ms 137880 KB Output is correct
17 Correct 93 ms 135996 KB Output is correct
18 Correct 88 ms 136352 KB Output is correct
19 Correct 72 ms 135776 KB Output is correct
20 Correct 71 ms 135656 KB Output is correct
21 Correct 91 ms 136564 KB Output is correct
22 Correct 84 ms 136528 KB Output is correct
23 Correct 98 ms 143176 KB Output is correct
24 Correct 103 ms 147080 KB Output is correct
25 Correct 70 ms 135764 KB Output is correct
26 Correct 70 ms 135612 KB Output is correct
27 Correct 96 ms 147792 KB Output is correct
28 Correct 96 ms 144720 KB Output is correct
29 Correct 93 ms 138324 KB Output is correct
30 Correct 94 ms 142928 KB Output is correct
31 Correct 92 ms 140464 KB Output is correct
32 Correct 90 ms 136592 KB Output is correct
33 Correct 93 ms 136568 KB Output is correct
34 Correct 97 ms 138836 KB Output is correct
35 Correct 93 ms 137300 KB Output is correct
36 Correct 96 ms 137704 KB Output is correct
37 Correct 76 ms 135700 KB Output is correct
38 Correct 69 ms 135764 KB Output is correct
39 Correct 154 ms 148152 KB Output is correct
40 Correct 163 ms 148048 KB Output is correct
41 Correct 178 ms 148052 KB Output is correct
42 Correct 174 ms 148464 KB Output is correct
43 Correct 201 ms 148208 KB Output is correct
44 Correct 200 ms 148048 KB Output is correct
45 Correct 102 ms 144488 KB Output is correct
46 Correct 99 ms 143952 KB Output is correct
47 Correct 144 ms 148052 KB Output is correct
48 Correct 144 ms 148052 KB Output is correct
49 Correct 172 ms 148312 KB Output is correct
50 Correct 144 ms 148052 KB Output is correct
51 Correct 157 ms 148132 KB Output is correct
52 Correct 178 ms 148128 KB Output is correct
53 Correct 191 ms 148136 KB Output is correct
54 Correct 204 ms 148052 KB Output is correct
55 Incorrect 87 ms 137848 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 136276 KB Output is correct
2 Correct 85 ms 136632 KB Output is correct
3 Correct 94 ms 143284 KB Output is correct
4 Correct 97 ms 146768 KB Output is correct
5 Correct 73 ms 135656 KB Output is correct
6 Correct 69 ms 135764 KB Output is correct
7 Correct 99 ms 148304 KB Output is correct
8 Correct 97 ms 144256 KB Output is correct
9 Correct 87 ms 136528 KB Output is correct
10 Correct 91 ms 143276 KB Output is correct
11 Correct 93 ms 140452 KB Output is correct
12 Correct 90 ms 137060 KB Output is correct
13 Correct 92 ms 136788 KB Output is correct
14 Correct 97 ms 137808 KB Output is correct
15 Correct 90 ms 138576 KB Output is correct
16 Correct 99 ms 137880 KB Output is correct
17 Correct 93 ms 135996 KB Output is correct
18 Correct 88 ms 136352 KB Output is correct
19 Correct 72 ms 135776 KB Output is correct
20 Correct 71 ms 135656 KB Output is correct
21 Correct 91 ms 136564 KB Output is correct
22 Correct 84 ms 136528 KB Output is correct
23 Correct 98 ms 143176 KB Output is correct
24 Correct 103 ms 147080 KB Output is correct
25 Correct 70 ms 135764 KB Output is correct
26 Correct 70 ms 135612 KB Output is correct
27 Correct 96 ms 147792 KB Output is correct
28 Correct 96 ms 144720 KB Output is correct
29 Correct 93 ms 138324 KB Output is correct
30 Correct 94 ms 142928 KB Output is correct
31 Correct 92 ms 140464 KB Output is correct
32 Correct 90 ms 136592 KB Output is correct
33 Correct 93 ms 136568 KB Output is correct
34 Correct 97 ms 138836 KB Output is correct
35 Correct 93 ms 137300 KB Output is correct
36 Correct 96 ms 137704 KB Output is correct
37 Correct 76 ms 135700 KB Output is correct
38 Correct 69 ms 135764 KB Output is correct
39 Correct 154 ms 148152 KB Output is correct
40 Correct 163 ms 148048 KB Output is correct
41 Correct 178 ms 148052 KB Output is correct
42 Correct 174 ms 148464 KB Output is correct
43 Correct 201 ms 148208 KB Output is correct
44 Correct 200 ms 148048 KB Output is correct
45 Correct 102 ms 144488 KB Output is correct
46 Correct 99 ms 143952 KB Output is correct
47 Correct 144 ms 148052 KB Output is correct
48 Correct 144 ms 148052 KB Output is correct
49 Correct 172 ms 148312 KB Output is correct
50 Correct 144 ms 148052 KB Output is correct
51 Correct 157 ms 148132 KB Output is correct
52 Correct 178 ms 148128 KB Output is correct
53 Correct 191 ms 148136 KB Output is correct
54 Correct 204 ms 148052 KB Output is correct
55 Incorrect 117 ms 142076 KB Output isn't correct
56 Halted 0 ms 0 KB -