QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876218#5713. Eggscavationsdds0 1ms10344kbC++142.6kb2025-01-30 18:40:372025-01-30 18:40:42

Judging History

This is the latest submission verdict.

  • [2025-01-30 18:40:42]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 10344kb
  • [2025-01-30 18:40:37]
  • Submitted

answer

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <vector>
#include <iomanip>
#include <queue>
#include <map>

#define ll int
#define maxn 2507

using namespace std;

ll n , K , m , T , q[maxn][maxn] , w[maxn][maxn] , fa[maxn][maxn] , X[maxn] , Y[maxn]; 
ll c[200000];

ll find( ll s1 , ll s2 ) { return ( fa[s1][s2] == s2 ? s2 : fa[s1][s2] = find( s1 , fa[s1][s2] ) ); }

void add( ll s1 , ll w )
{
	if( s1 == 0 ) return;
	while( s1 <= m ) {
		c[s1] += w; s1 += ( s1 & -s1 );
	}
}

void del( ll x , ll s1 , ll s2 )
{
	int now = find( x , s1 );
	while( now <= s2 ) {
		add( w[x][now] , -1 ); fa[x][now] = now + 1; now = find( x , now ); 
	}
}

ll ask( ll s1 )
{
	ll sum = 0;
	while( s1 ) {
		sum += c[s1]; s1 -= ( s1 & -s1 );
	}
	return sum;
}

int main()
{
	ios :: sync_with_stdio( false );
	cin.tie( 0 );
	cin >> n >> K >> m; if( n > 40 ) return 0;
	for( int i = 1 ; i <= m ; ++i ) {
		ll tmp; cin >> tmp;
		for( int j = 0 ; j < tmp ; ++j ) {
			cin >> X[j] >> Y[j];
		}
		for( int j = 1 ; j < ( 1 << tmp ) ; ++j ) {
			ll mnx , mxx , mny , mxy; mnx = mny = 1; mxx = mxy = n; ll sum = 0;
			for( int k = 0 ; k < tmp ; ++k )
				if( j & (1<<k) ) {
					sum ++; mnx = max( mnx , X[k] ); mxx = min( mxx , X[k] + K - 1 );
					mny = max( mny , Y[k] ); mxy = min( mxy , Y[k] + K - 1 );
				}
			sum = ( sum % 2 ? 1 : -1 ); 
			if( mnx <= mxx && mny <= mxy ) {
				q[mnx][mny] += sum; q[mxx + 1][mny] -= sum; q[mnx][mxy + 1] -= sum; 
				q[mxx + 1][mxy + 1] += sum;
			}
		}
			for( int j = 1 ; j <= n ; ++j )
		for( int k = 1 ; k <= n ; ++k )
			q[j][k] += q[j - 1][k] + q[j][k - 1] - q[j - 1][k - 1];
			for( int j = 1 ; j <= n ; ++j )
		for( int k = 1 ; k <= n ; ++k ) {
			if( q[j][k] > 1 ) cout << 0/0;
			w[j][k] += q[j][k];
			q[j][k] = 0;
		}
	}
	for( int j = 1 ; j <= n ; ++j )
		for( int k = 1 ; k <= n ; ++k )
			q[j][k] += q[j - 1][k] + q[j][k - 1] - q[j - 1][k - 1];
	for( int i = 1 ; i <= n ; ++i ) for( int j = 1 ; j <= n + 1 ; ++j ) fa[i][j] = j;//w[i][j] = q[i][j];
	for( int i = K ; i <= n ; ++i ) for( int j = K ; j <= n ; ++j ) if( w[i][j] ) add( w[i][j] , 1 );
	cin >> T;
	while( T -- ) {
		ll opt , x , y;
		cin >> opt;
		if( opt == 1 ) {
			cin >> x >> y;
			for( int i = x ; i <= min( n , x + K - 1 ) ; ++i )
				del( i , y , min( n , y + K - 1 ) );
		}else {
			ll sum= 0; cin>> x;
			if( x > m ) {
				sum = 0;
			}else sum = ask( m ) - ask( x - 1 );
			cout << fixed << setprecision( 5 ) << (double)sum / (double)( (n-K+1)*(n-K+1)) <<"\n";
		}
	}
	return 0;
 } 

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 3.75
Accepted
time: 1ms
memory: 10344kb

input:

40 5
200
4 25 33 8 25 39 17 7 5
2 25 11 25 17
3 1 21 1 1 25 40
1 1 1
4 25 11 25 18 35 25 16 1
3 6 9 39 1 1 33
1 1 27
1 37 21
3 1 31 25 1 40 13
3 11 33 31 1 21 39
4 36 16 31 17 16 5 31 22
2 3 9 36 19
1 39 25
2 7 11 17 23
2 25 11 3 15
1 29 12
1 37 21
2 1 26 7 36
3 27 5 1 26 35 33
1 37 36
3 15 31 4 1 3...

output:

0.90509
0.88272
0.82330
0.70756
0.58025
0.42978
0.29784
0.20602
0.14043
0.08102
0.04707
0.02315
0.01235
0.00617
0.00540
0.00386
0.00154
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 202 numbers

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 8432kb

input:

40 4
500
1 1 17
3 5 34 21 25 6 39
4 39 31 15 1 3 11 21 21
1 37 21
3 16 2 33 29 36 19
3 12 25 1 5 32 1
3 15 16 31 5 21 11
2 11 19 13 17
1 3 13
1 2 21
1 1 13
1 30 36
1 21 1
1 25 23
3 19 25 37 23 25 9
1 14 1
4 13 33 3 23 2 13 11 6
1 21 3
1 9 25
2 29 11 31 23
1 16 33
1 1 19
4 1 11 17 39 36 37 16 1
1 1 2...

output:

0.90577
0.90066
0.88751
0.85464
0.81008
0.72900
0.63696
0.53178
0.43901
0.32432
0.24690
0.17969
0.12637
0.08985
0.06428
0.04894
0.03652
0.02264
0.01607
0.01096
0.00657
0.00511
0.00438
0.00438
0.00219
0.00073
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

wrong answer 1st numbers differ - expected: '0.90869', found: '0.90577', error = '0.00292'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

999 300
10000
1 667 804
3 769 412 909 315 471 651
1 869 932
4 404 590 541 271 36 897 244 108
1 963 94
1 269 811
1 595 213
1 25 284
3 439 438 295 715 279 962
1 216 784
1 568 255
3 2 597 406 118 298 177
1 936 559
1 976 187
2 989 163 306 923
3 391 211 513 163 968 193
2 22 670 524 543
1 65 371
3 7 619 8...

output:


result:

wrong output format Unexpected end of file - double expected

Subtask #3:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

2500 1111
4000
1 751 1336
2 1077 2296 1305 1997
1 161 2337
3 75 720 1197 1725 2311 1609
1 2149 1221
3 105 1711 1961 1727 1181 2055
1 1913 871
2 1164 924 783 486
3 215 1722 1621 1807 1638 1176
4 801 1989 483 1149 561 878 261 2245
4 839 2247 526 2413 573 2431 1218 775
3 2201 909 1002 197 778 2451
1 40...

output:


result:

wrong output format Unexpected end of file - double expected