oj.uz

Submission #365959

# Submission time Handle Problem Language Result Execution time Memory
365959 2021-02-12T15:20:48 Z Ahmadsm2005 Trampoline (info1cup20_trampoline) C++14
54 / 100
 2000 ms 2668 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define modulo 998244353
//#define int long long
#define PI acos(-1)
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#define sinDegrees(x) sin((x) * PI / 180.0)
#define cosDegrees(x) cos((x) * PI / 180.0)
#define tanDegrees(x) tan((x) * PI / 180.0)
#define atanDegrees(x) atan(x)* 180.0 / PI
#define asinDegrees(x) asin(x)* 180.0 / PI
#define EPS 0.000000001
using namespace std;
int power(int x,int y,int m)
{
int temp;
if(y == 0)
return 1;
temp = (power(x, y/2,m))%m;
if (y%2 == 0)
return ((temp%m)*temp);
else
return ((x*temp%m)*temp%m)%m;
}
int inv(int x,int m=modulo)
{
return (power(x,m-2,m))%m;
}
///IOI 2021 isA
int R,C,N,T,X,Y,X2,Y2;
pair<int,int>lolz[200001],lolq;
int32_t main()
{
//freopen("output.txt","w",stdout);
//freopen("sorting.in","r",stdin);
cin.tie(0),iostream::sync_with_stdio(0);
cin>>R>>C>>N;
for(int i=0;i<N;i++){
cin>>Y>>X;
lolz[i]={Y,X};
}
sort(lolz,lolz+N);
cin>>T;
while(T--){
cin>>Y>>X>>Y2>>X2;
int LASTX=X;
if(Y2<Y){
cout<<"NO"<<endl;
goto a;
}
if(Y-Y2>N){
cout<<"NO"<<endl;
goto a;
}
for(int i=Y;i<Y2;i++){
int L=0,R=N-1,mid,BEST=INT_MAX;
while(L<=R){
mid=(L+R)/2;
lolq=lolz[mid];
if(lolq.first<i)
L=mid+1;
else if(lolq.first>i)
R=mid-1;
else if(lolq.second<LASTX)
L=mid+1;
else
BEST=min(BEST,lolq.second),R=mid-1;
}
LASTX=BEST;
}
if(LASTX<=X2){
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
a:;
}
return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB 200 token(s): yes count is 21, no count is 179
2 Correct 4 ms 364 KB 200 token(s): yes count is 70, no count is 130
3 Correct 3 ms 364 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 1900 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 410 ms 2028 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 224 ms 2028 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 455 ms 1960 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 2600 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 205 ms 2668 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 206 ms 2668 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 224 ms 2668 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 215 ms 2668 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 213 ms 2668 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 748 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 58 ms 364 KB 5000 token(s): yes count is 3837, no count is 1163
3 Execution timed out 2080 ms 364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -