oj.uz

답안 #530503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530503 2022-02-25T15:25:33 Z Killer2501 Trampoline (info1cup20_trampoline) C++14
100 / 100
 369 ms 41072 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 1e2+2;
const int mod = 1e9+7;
const ll base = 75;
const int inf = 1e9;
int m, n, t, b[N], d[N], lab[N], q;
int k, a[N], dp[N], P[N][20];
ll ans, tong;
vector<int> adj[N];
vector<int> vi;
string s[N];
bool vis[N];
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n&1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
void add(int &x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
}
int findp(int u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(int u, int v)
{
    u = findp(u);
    v = findp(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}
int C(int u, int v)
{
    if(u > v)return 0;
    return 1ll * a[v] * b[u] % mod * b[v-u] % mod;
}
pii p[N];
void sol()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i ++)cin >> p[i].fi >> p[i].se;
    sort(p+1, p+1+k);
    for(int i = 1; i <= k; i ++)
    {
        int j = lower_bound(p+1, p+1+k, make_pair(p[i].fi+1, p[i].se)) - p;
        if(j <= k && p[j].fi == p[i].fi+1)P[i][0] = j;
        //cout << i <<" "<<j<<'\n';
    }
    for(int j = 1; j <= 18; j ++)
    {
        for(int i = 1; i <= k; i ++)P[i][j] = P[P[i][j-1]][j-1];
    }
    cin >> q;
    while(q -- > 0)
    {
        pii l, r;
        cin >> l.fi >> l.se >> r.fi >> r.se;
        if(l.fi > r.fi || l.se > r.se)cout << "No" << '\n';
        else if(l.fi == r.fi)cout << "Yes" << '\n';
        else
        {
            int i = lower_bound(p+1, p+1+k, l) - p;

            if(i > k || l.fi != p[i].fi)cout << "No" << '\n';
            else
            {
                for(int j = 18; j >= 0; j --)
                {
                    if(P[i][j] && p[P[i][j]].fi < r.fi-1)i = P[i][j];
                }
                if(p[i].fi < r.fi-1 && P[i][0])i = P[i][0];
                if(p[i].fi == r.fi-1 && p[i].se <= r.se)cout << "Yes" << '\n';
                else cout << "No" << '\n';
            }
        }
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:105:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:106:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11980 KB 200 token(s): yes count is 21, no count is 179
2 Correct 9 ms 12196 KB 200 token(s): yes count is 70, no count is 130
3 Correct 8 ms 11948 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 28464 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 96 ms 30244 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 94 ms 30136 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 98 ms 30432 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 29128 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 232 ms 40932 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 231 ms 40768 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 255 ms 40880 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 259 ms 40844 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 275 ms 40756 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11724 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 10 ms 11980 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 10 ms 11980 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 11 ms 11980 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 11 ms 11980 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 14 ms 11948 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 29148 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 325 ms 40900 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 258 ms 40872 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 363 ms 40800 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 273 ms 40940 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 242 ms 40900 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 248 ms 41072 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 231 ms 40996 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 329 ms 40808 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 356 ms 40824 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 358 ms 40824 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 221 ms 40992 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 217 ms 40852 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 259 ms 40932 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 222 ms 40856 KB 200000 token(s): yes count is 129674, no count is 70326