oj.uz

Submission #577071

# Submission time Handle Problem Language Result Execution time Memory
577071 2022-06-14T02:02:03 Z AGE Checker (COCI19_checker) C++14
23 / 110
 539 ms 58656 KB 
#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back

using namespace std;
const int N=1e6,M=3e3+2,mod=1e9+7;
int numofc[N],numofo[N],seg[N],seg2[N],seg3[N];
int x[N],y[N],z[N];
vector< pair<int,int> > v[N];
void update(int v,int tl,int tr,int index){

    if(tl==tr){

        /*if(seg[v]==0)
            seg2[v]=1;

        else
            seg3[v]=1;*/

        seg[v]=!seg[v];

        return ;

    }

    int tm=(tl+tr)/2;

    if(index<=tm)
        update(v*2,tl,tm,index);

    else
        update(v*2+1,tm+1,tr,index);

    seg[v]=seg[v*2]+seg[v*2+1];
    /*seg2[v]=seg2[v*2]+seg2[v*2+1];
    seg3[v]=seg3[v*2]+seg3[v*2+1];*/


}

int get(int v,int tl,int tr,int l,int r){

    if(tl>r||tr<l)
        return 0;

    if(tl>=l&&tr<=r)
        return seg[v];

    int tm=(tl+tr)/2;

    return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r);

}
main(){

    int xx;
    cin>>xx;

    int n;
    cin>>n;


    string s;
    cin>>s;

    map<int,int>mp;

    for(int i=0;i<n-3;i++){

        cin>>x[i]>>y[i]>>z[i];

        v[min(x[i],y[i])].pb({1,i+1});
        v[max(x[i],y[i])].pb({0,i+1});

    }


    bool Final_ans=0;

    for(int i=1;i<=n;i++){

        for(auto x:v[i])
            if(x.F==0)
                update(1,1,n,mp[x.S]);

        for(auto x:v[i]){

            if(x.F==1)
                continue;

            int xxx=get(1,1,n,mp[x.S]+1,i);
            if(xxx!=0)
                Final_ans=1;

        }

        for(auto x:v[i]){
            if(x.F==1)
                mp[x.S]=i,update(1,1,n,i);
        }

    }

    if(Final_ans==1)
        cout<<"neispravna triangulacija"<<endl;

    else
        cout<<"tocno"<<endl;


    return 0;

}

Compilation message

checker.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 15 ms 23752 KB Output is correct
3 Incorrect 12 ms 23764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 15 ms 23752 KB Output is correct
3 Incorrect 12 ms 23764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 58560 KB Output is correct
2 Correct 476 ms 58460 KB Output is correct
3 Correct 522 ms 58524 KB Output is correct
4 Correct 505 ms 58656 KB Output is correct
5 Correct 476 ms 58576 KB Output is correct
6 Correct 481 ms 58140 KB Output is correct
7 Correct 411 ms 54184 KB Output is correct
8 Correct 460 ms 56116 KB Output is correct
9 Correct 469 ms 55104 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 58460 KB Output is correct
2 Correct 508 ms 58588 KB Output is correct
3 Incorrect 463 ms 58508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 15 ms 23752 KB Output is correct
3 Incorrect 12 ms 23764 KB Output isn't correct
4 Halted 0 ms 0 KB -