Submission #342493

#	Time	Username	Problem	Language	Result	Execution time	Memory
342493		mario05092929	The Potion of Great Power (CEOI20_potion)	C++11	18 / 100	631 ms	44628 KiB

potion

#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 (stderr)

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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30