oj.uz

Submission #544965

# Submission time Handle Problem Language Result Execution time Memory
544965 2022-04-03T08:40:06 Z zaneyu Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 123 ms 16704 KB 
#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("O2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
vector<int> v[maxn],v2[maxn];
vector<int> bad[maxn];
int l=INF,r=0;
void init(int n, int C, int x, int y, int M, char *S) {
    v[x].pb(y);
    MNTO(l,y),MXTO(r,y);
    REP(i,M){
        if(S[i]=='N') --x;
        else if(S[i]=='S') ++x;
        else if(S[i]=='E') ++y;
        else --y;
        v[x].pb(y);
        MNTO(l,y),MXTO(r,y);
    }
    REP1(i,n){
        SORT_UNIQUE(v[i]);
        bad[i]=v[i];
        vector<int> vv;
        REP(j,sz(v[i])){
            int p=j;
            while(j<sz(v[i]) and v[i][j]-v[i][p]==j-p) ++j;
            --j;
            v2[i].pb(v[i][j]);
            vv.pb(v[i][p]);
        }
        //cout<<vv<<'\n';
        v[i]=vv;
    }
}
bool is(int x,int y){
    return (((lower_bound(ALL(bad[x]),y)!=bad[x].end()) and (*lower_bound(ALL(bad[x]),y))==y));
}
int colour(int ar, int ac, int br, int bc) {
    int ans=0;
    if(ar!=br){
        if(ac<l){
            if(is(2,l) and is(1,l)) ++ans;
            ac=l;
        }
        if(bc>r){
            if(is(2,r) and is(1,r)) ++ans;
            bc=r;
        }
    }
    //cout<<ac<<' '<<bc<<'\n';
    for(int i=ar;i<=br;i++){
        /*bool cur=1;
        for(int j=ac;j<=bc;j++){
            if(!is(i,j) and cur) ++ans;
            cur=is(i,j);
        }*/
        int d=(lower_bound(ALL(v2[i]),bc)-v2[i].begin())-(lower_bound(ALL(v2[i]),ac)-v2[i].begin());
            ans+=d;
            if(!is(i,ac)) ++ans;
            //if(!is(i,bc)) ++ans;
        
    }
        //cout<<ans<<' ';
    
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7360 KB Output is correct
3 Correct 96 ms 11408 KB Output is correct
4 Correct 123 ms 11900 KB Output is correct
5 Correct 100 ms 11908 KB Output is correct
6 Correct 88 ms 11756 KB Output is correct
7 Correct 94 ms 11952 KB Output is correct
8 Correct 67 ms 11572 KB Output is correct
9 Correct 123 ms 11880 KB Output is correct
10 Correct 102 ms 11828 KB Output is correct
11 Correct 92 ms 11764 KB Output is correct
12 Correct 61 ms 11824 KB Output is correct
13 Correct 62 ms 11860 KB Output is correct
14 Correct 66 ms 11880 KB Output is correct
15 Correct 71 ms 11732 KB Output is correct
16 Correct 72 ms 11528 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Runtime error 13 ms 16704 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -