oj.uz

Submission #892912

# Submission time Handle Problem Language Result Execution time Memory
892912 2023-12-26T07:20:10 Z thunopro Food Court (JOI21_foodcourt) C++14
14 / 100
 193 ms 148308 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 = T [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" ; 
		}
	}
}
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 () ; 
}

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 71 ms 136276 KB Output is correct
2 Correct 74 ms 136532 KB Output is correct
3 Correct 79 ms 143092 KB Output is correct
4 Correct 85 ms 146772 KB Output is correct
5 Correct 61 ms 135868 KB Output is correct
6 Correct 60 ms 135760 KB Output is correct
7 Correct 87 ms 148308 KB Output is correct
8 Correct 86 ms 143792 KB Output is correct
9 Correct 80 ms 136468 KB Output is correct
10 Correct 84 ms 143448 KB Output is correct
11 Correct 85 ms 140644 KB Output is correct
12 Correct 78 ms 136800 KB Output is correct
13 Correct 84 ms 136792 KB Output is correct
14 Correct 88 ms 137812 KB Output is correct
15 Correct 87 ms 138816 KB Output is correct
16 Correct 86 ms 137812 KB Output is correct
17 Correct 74 ms 136020 KB Output is correct
18 Correct 77 ms 136248 KB Output is correct
19 Correct 61 ms 135764 KB Output is correct
20 Correct 62 ms 135656 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 136276 KB Output is correct
2 Correct 74 ms 136532 KB Output is correct
3 Correct 79 ms 143092 KB Output is correct
4 Correct 85 ms 146772 KB Output is correct
5 Correct 61 ms 135868 KB Output is correct
6 Correct 60 ms 135760 KB Output is correct
7 Correct 87 ms 148308 KB Output is correct
8 Correct 86 ms 143792 KB Output is correct
9 Correct 80 ms 136468 KB Output is correct
10 Correct 84 ms 143448 KB Output is correct
11 Correct 85 ms 140644 KB Output is correct
12 Correct 78 ms 136800 KB Output is correct
13 Correct 84 ms 136792 KB Output is correct
14 Correct 88 ms 137812 KB Output is correct
15 Correct 87 ms 138816 KB Output is correct
16 Correct 86 ms 137812 KB Output is correct
17 Correct 74 ms 136020 KB Output is correct
18 Correct 77 ms 136248 KB Output is correct
19 Correct 61 ms 135764 KB Output is correct
20 Correct 62 ms 135656 KB Output is correct
21 Correct 74 ms 136396 KB Output is correct
22 Correct 80 ms 136792 KB Output is correct
23 Correct 83 ms 143076 KB Output is correct
24 Correct 93 ms 147064 KB Output is correct
25 Correct 62 ms 135736 KB Output is correct
26 Correct 62 ms 135668 KB Output is correct
27 Correct 87 ms 147824 KB Output is correct
28 Correct 84 ms 144716 KB Output is correct
29 Correct 84 ms 138332 KB Output is correct
30 Correct 93 ms 142932 KB Output is correct
31 Correct 81 ms 140456 KB Output is correct
32 Correct 79 ms 136604 KB Output is correct
33 Correct 81 ms 136636 KB Output is correct
34 Correct 96 ms 139232 KB Output is correct
35 Correct 82 ms 137300 KB Output is correct
36 Correct 86 ms 137932 KB Output is correct
37 Correct 60 ms 135764 KB Output is correct
38 Correct 62 ms 135848 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 147444 KB Output is correct
2 Correct 155 ms 147288 KB Output is correct
3 Correct 165 ms 147448 KB Output is correct
4 Correct 164 ms 147632 KB Output is correct
5 Correct 190 ms 147288 KB Output is correct
6 Correct 193 ms 147480 KB Output is correct
7 Correct 85 ms 142676 KB Output is correct
8 Correct 92 ms 142676 KB Output is correct
9 Correct 135 ms 147280 KB Output is correct
10 Correct 138 ms 147284 KB Output is correct
11 Correct 136 ms 147284 KB Output is correct
12 Correct 143 ms 147516 KB Output is correct
13 Correct 149 ms 147028 KB Output is correct
14 Correct 163 ms 147288 KB Output is correct
15 Correct 193 ms 147580 KB Output is correct
16 Correct 190 ms 147532 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 136276 KB Output is correct
2 Correct 74 ms 136532 KB Output is correct
3 Correct 79 ms 143092 KB Output is correct
4 Correct 85 ms 146772 KB Output is correct
5 Correct 61 ms 135868 KB Output is correct
6 Correct 60 ms 135760 KB Output is correct
7 Correct 87 ms 148308 KB Output is correct
8 Correct 86 ms 143792 KB Output is correct
9 Correct 80 ms 136468 KB Output is correct
10 Correct 84 ms 143448 KB Output is correct
11 Correct 85 ms 140644 KB Output is correct
12 Correct 78 ms 136800 KB Output is correct
13 Correct 84 ms 136792 KB Output is correct
14 Correct 88 ms 137812 KB Output is correct
15 Correct 87 ms 138816 KB Output is correct
16 Correct 86 ms 137812 KB Output is correct
17 Correct 74 ms 136020 KB Output is correct
18 Correct 77 ms 136248 KB Output is correct
19 Correct 61 ms 135764 KB Output is correct
20 Correct 62 ms 135656 KB Output is correct
21 Correct 133 ms 147444 KB Output is correct
22 Correct 155 ms 147288 KB Output is correct
23 Correct 165 ms 147448 KB Output is correct
24 Correct 164 ms 147632 KB Output is correct
25 Correct 190 ms 147288 KB Output is correct
26 Correct 193 ms 147480 KB Output is correct
27 Correct 85 ms 142676 KB Output is correct
28 Correct 92 ms 142676 KB Output is correct
29 Correct 135 ms 147280 KB Output is correct
30 Correct 138 ms 147284 KB Output is correct
31 Correct 136 ms 147284 KB Output is correct
32 Correct 143 ms 147516 KB Output is correct
33 Correct 149 ms 147028 KB Output is correct
34 Correct 163 ms 147288 KB Output is correct
35 Correct 193 ms 147580 KB Output is correct
36 Correct 190 ms 147532 KB Output is correct
37 Incorrect 78 ms 139028 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 136276 KB Output is correct
2 Correct 74 ms 136532 KB Output is correct
3 Correct 79 ms 143092 KB Output is correct
4 Correct 85 ms 146772 KB Output is correct
5 Correct 61 ms 135868 KB Output is correct
6 Correct 60 ms 135760 KB Output is correct
7 Correct 87 ms 148308 KB Output is correct
8 Correct 86 ms 143792 KB Output is correct
9 Correct 80 ms 136468 KB Output is correct
10 Correct 84 ms 143448 KB Output is correct
11 Correct 85 ms 140644 KB Output is correct
12 Correct 78 ms 136800 KB Output is correct
13 Correct 84 ms 136792 KB Output is correct
14 Correct 88 ms 137812 KB Output is correct
15 Correct 87 ms 138816 KB Output is correct
16 Correct 86 ms 137812 KB Output is correct
17 Correct 74 ms 136020 KB Output is correct
18 Correct 77 ms 136248 KB Output is correct
19 Correct 61 ms 135764 KB Output is correct
20 Correct 62 ms 135656 KB Output is correct
21 Correct 74 ms 136396 KB Output is correct
22 Correct 80 ms 136792 KB Output is correct
23 Correct 83 ms 143076 KB Output is correct
24 Correct 93 ms 147064 KB Output is correct
25 Correct 62 ms 135736 KB Output is correct
26 Correct 62 ms 135668 KB Output is correct
27 Correct 87 ms 147824 KB Output is correct
28 Correct 84 ms 144716 KB Output is correct
29 Correct 84 ms 138332 KB Output is correct
30 Correct 93 ms 142932 KB Output is correct
31 Correct 81 ms 140456 KB Output is correct
32 Correct 79 ms 136604 KB Output is correct
33 Correct 81 ms 136636 KB Output is correct
34 Correct 96 ms 139232 KB Output is correct
35 Correct 82 ms 137300 KB Output is correct
36 Correct 86 ms 137932 KB Output is correct
37 Correct 60 ms 135764 KB Output is correct
38 Correct 62 ms 135848 KB Output is correct
39 Correct 133 ms 147444 KB Output is correct
40 Correct 155 ms 147288 KB Output is correct
41 Correct 165 ms 147448 KB Output is correct
42 Correct 164 ms 147632 KB Output is correct
43 Correct 190 ms 147288 KB Output is correct
44 Correct 193 ms 147480 KB Output is correct
45 Correct 85 ms 142676 KB Output is correct
46 Correct 92 ms 142676 KB Output is correct
47 Correct 135 ms 147280 KB Output is correct
48 Correct 138 ms 147284 KB Output is correct
49 Correct 136 ms 147284 KB Output is correct
50 Correct 143 ms 147516 KB Output is correct
51 Correct 149 ms 147028 KB Output is correct
52 Correct 163 ms 147288 KB Output is correct
53 Correct 193 ms 147580 KB Output is correct
54 Correct 190 ms 147532 KB Output is correct
55 Incorrect 78 ms 139028 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 136276 KB Output is correct
2 Correct 74 ms 136532 KB Output is correct
3 Correct 79 ms 143092 KB Output is correct
4 Correct 85 ms 146772 KB Output is correct
5 Correct 61 ms 135868 KB Output is correct
6 Correct 60 ms 135760 KB Output is correct
7 Correct 87 ms 148308 KB Output is correct
8 Correct 86 ms 143792 KB Output is correct
9 Correct 80 ms 136468 KB Output is correct
10 Correct 84 ms 143448 KB Output is correct
11 Correct 85 ms 140644 KB Output is correct
12 Correct 78 ms 136800 KB Output is correct
13 Correct 84 ms 136792 KB Output is correct
14 Correct 88 ms 137812 KB Output is correct
15 Correct 87 ms 138816 KB Output is correct
16 Correct 86 ms 137812 KB Output is correct
17 Correct 74 ms 136020 KB Output is correct
18 Correct 77 ms 136248 KB Output is correct
19 Correct 61 ms 135764 KB Output is correct
20 Correct 62 ms 135656 KB Output is correct
21 Correct 74 ms 136396 KB Output is correct
22 Correct 80 ms 136792 KB Output is correct
23 Correct 83 ms 143076 KB Output is correct
24 Correct 93 ms 147064 KB Output is correct
25 Correct 62 ms 135736 KB Output is correct
26 Correct 62 ms 135668 KB Output is correct
27 Correct 87 ms 147824 KB Output is correct
28 Correct 84 ms 144716 KB Output is correct
29 Correct 84 ms 138332 KB Output is correct
30 Correct 93 ms 142932 KB Output is correct
31 Correct 81 ms 140456 KB Output is correct
32 Correct 79 ms 136604 KB Output is correct
33 Correct 81 ms 136636 KB Output is correct
34 Correct 96 ms 139232 KB Output is correct
35 Correct 82 ms 137300 KB Output is correct
36 Correct 86 ms 137932 KB Output is correct
37 Correct 60 ms 135764 KB Output is correct
38 Correct 62 ms 135848 KB Output is correct
39 Correct 133 ms 147444 KB Output is correct
40 Correct 155 ms 147288 KB Output is correct
41 Correct 165 ms 147448 KB Output is correct
42 Correct 164 ms 147632 KB Output is correct
43 Correct 190 ms 147288 KB Output is correct
44 Correct 193 ms 147480 KB Output is correct
45 Correct 85 ms 142676 KB Output is correct
46 Correct 92 ms 142676 KB Output is correct
47 Correct 135 ms 147280 KB Output is correct
48 Correct 138 ms 147284 KB Output is correct
49 Correct 136 ms 147284 KB Output is correct
50 Correct 143 ms 147516 KB Output is correct
51 Correct 149 ms 147028 KB Output is correct
52 Correct 163 ms 147288 KB Output is correct
53 Correct 193 ms 147580 KB Output is correct
54 Correct 190 ms 147532 KB Output is correct
55 Incorrect 110 ms 144976 KB Output isn't correct
56 Halted 0 ms 0 KB -