oj.uz

Submission #342493

# Submission time Handle Problem Language Result Execution time Memory
342493 2021-01-02T09:05:38 Z mario05092929 The Potion of Great Power (CEOI20_potion) C++11
18 / 100
 631 ms 44628 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;

vector <pi> v[100005][2],v2[100005][2];
int n,m,d,a[100005];
vecpi edge;
map <pi,int> la;

void init(int N, int D, int H[]) {
    n = N, d = D;
    for(int i = 0;i < n;i++) {
        a[i+1] = H[i];
    }
}

void curseChanges(int U, int A[], int B[]) {
    m = U;
    for(int i = 0;i < m;i++) edge.pb({A[i]+1,B[i]+1});
    int time = 1;
    for(pi &i : edge) {
        if(i.x > i.y) swap(i.x,i.y);
        if(la[i] != 0) {
            v2[i.x][a[i.y]].pb({la[i],time-1});
            v2[i.y][a[i.x]].pb({la[i],time-1});
            la[i] = 0;
        }
        else la[i] = time;
        time++;
    }
    for(pi i : edge) {
        if(la[i] != 0) {
            v2[i.x][a[i.y]].pb({la[i],time-1});
            v2[i.y][a[i.x]].pb({la[i],time-1});
            la[i] = 0;
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j < 2;j++) {
            if(v2[i][j].empty()) continue;
            sort(all(v2[i][j]));
            int l = 0,r = 0;
            for(pi k : v2[i][j]) {
                if(r < k.x) {
                    if(l) v[i][j].pb({l,r});
                    l = k.x, r = k.y;
                }
                r = max(r,k.y);
            }
            v[i][j].pb({l,r});
        }
    }
}

int question(int x,int y,int day) {
    x++, y++;
    auto itx0 = upper_bound(all(v[x][0]),make_pair(day,INF));
    auto ity0 = upper_bound(all(v[y][0]),make_pair(day,INF));
    auto itx1 = upper_bound(all(v[x][1]),make_pair(day,INF));
    auto ity1 = upper_bound(all(v[y][1]),make_pair(day,INF));
    int hex = 0,hey = 0;
    if(itx0 != v[x][0].begin()&&(*prev(itx0)).y >= day) hex = 1;
    if(itx1 != v[x][1].begin()&&(*prev(itx1)).y >= day) hex = 1;
    if(ity0 != v[y][0].begin()&&(*prev(ity0)).y >= day) hey = 1;
    if(ity1 != v[y][1].begin()&&(*prev(ity1)).y >= day) hey = 1;
    if(!hex||!hey) return INF;

    if(itx0 != v[x][0].begin()&&ity0 != v[y][0].begin()) {
        itx0--, ity0--;
        if((*itx0).y >= day&&(*ity0).y >= day) return 0;
    }
    if(itx1 != v[x][1].begin()&&ity1 != v[y][1].begin()) {
        itx1--, ity1--;
        if((*itx1).y >= day&&(*ity1).y >= day) return 0;
    }
    return 1;
}

Compilation message

potion.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
potion.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
potion.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9728 KB Incorrect

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 19692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 44628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 38360 KB Output is correct
2 Correct 267 ms 21476 KB Output is correct
3 Correct 430 ms 27492 KB Output is correct
4 Correct 436 ms 27364 KB Output is correct
5 Correct 612 ms 38244 KB Output is correct
6 Correct 425 ms 27236 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 21100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9728 KB Incorrect