QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#821066#9905. 哈夫曼树QZJ123456Compile Error//C++146.0kb2024-12-19 12:29:192024-12-19 12:29:19

Judging History

你现在查看的是最新测评结果

  • [2024-12-19 12:29:19]
  • 评测
查看
  • [2024-12-19 12:29:19]
  • 提交

answer

#include <cstdio>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,popcnt,tune=native")
#include<bits/stdc++.h>
#define sit multiset<node>::iterator
typedef long long ll;
using namespace std;
struct freader {
    FILE *f;
#   ifdef ONLINE_JUDGE
    char buf[1048577], *p1, *p2;
#       define fgetc(f) (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1048576, f), p1 == p2) ? EOF : *p1++)
#   endif
#   ifdef BOOLTRANS
    bool neof;
#       define NEOF(c) ((c) != EOF || (neof = 0))
#   else
#       define NEOF(c) ((c) != EOF)
#   endif
    freader(FILE *_f = stdin) : f(_f) {
#       ifdef BOOLTRANS
        neof = 1;
#       endif
#       ifdef ONLINE_JUDGE
        setvbuf(f, NULL, _IONBF, 0);
        p1 = p2 = buf;
#       endif
    }
    void read(char &x) {
        for (x = fgetc(f); NEOF(x) && x <= ' '; x = fgetc(f));
        return;
    }
    void read(char *s) {
        for (*s = fgetc(f); NEOF(*s) && *s <= ' '; *s = fgetc(f));
        for (s++; NEOF(*s = fgetc(f)) && *s > ' '; s++);
        *s = '\0';
        return;
    }
    void read(float x) {return fputs("Error: Unable to read float.", stderr), void();}
    void read(double x) {return fputs("Error: Unable to read double.", stderr), void();}
    void read(long double x) {return fputs("Error: Unable to read long double.", stderr), void();}
    template<typename T> void read(T &x) {
        char c(fgetc(f));
#       ifdef NEGATIVE
        for (; NEOF(c) && (c < '0' || c > '9') && c != '-'; c = fgetc(f));
        if (c == '-')
            for (c = fgetc(f), x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) - (c ^ '0');
        else
            for (x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) + (c ^ '0');
#       else
        for (; NEOF(c) && (c < '0' || c > '9'); c = fgetc(f));
        for (x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) + (c ^ '0');
#       endif
        return;
    }
#   if __cplusplus >= 201103
    template<typename T, typename...Args> void read(T &x, Args &...args) {return read(x), read(args...);}
#   endif
    template<typename T> freader &operator >> (T &x) {
#       ifdef BOOLTRANS
        return *this ? read(x), *this : *this;
#       else
        return read(x), *this;
#       endif
    }
#   ifdef BOOLTRANS
    operator bool() {return neof;}
#   endif
#   ifdef ONLINE_JUDGE
#       undef fgetc
#   endif
#   undef NEOF
} fin;
struct fwriter {
    FILE *f;
#   ifdef ONLINE_JUDGE
    char buf[1048577], *p1;
#       define fputc(c, f) (p1 == buf + 1048576 ? fwrite(buf, 1, 1048576, f), *(p1 = buf)++ = (c) : *p1++ = (c))
#   endif
    fwriter(FILE *_f = stdout): f(_f) {
#       ifdef ONLINE_JUDGE
        setvbuf(f, NULL, _IONBF, 0);
        p1 = buf;
#       endif
    }
    ~fwriter() {flush();}
    void flush() {
#       ifdef ONLINE_JUDGE
        fwrite(buf, 1, p1 - buf, f), p1 = buf;
#       else
        fflush(f);
#       endif
        return;
    }
    void write(char c) {return fputc(c, f), void();}
    void write(char *s) {
        for (; *s; s++) fputc(*s, f);
        return;
    }
    void write(const char *s) {
        for (; *s; s++) fputc(*s, f);
        return;
    }
    void write(float x) {return fputs("Error: Unable to write float.", stderr), void();}
    void write(double x) {return fputs("Error: Unable to write double.", stderr), void();}
    void write(long double x) {return fputs("Error: Unable to write long double.", stderr), void();}
    template<typename T> void write(T x) {
        if (!x) return fputc('0', f), void();
        if (x < 0) fputc('-', f), x = -x;
        char s[41];
        int l(0);
        while (x) s[l++] = x % 10 ^ '0', x /= 10;
        while (l--) fputc(s[l], f);
        return;
    }
#   if __cplusplus >= 201103
    template<typename T, typename...Args> void write(T x, Args...args) {return write(x), write(args...);}
#   endif
    template<typename T> fwriter &operator << (T x) {return write(x), *this;}
#   ifdef ONLINE_JUDGE
#       undef fputc
#   endif
} fout;
struct node{
	ll l,r;
	node(ll l_,ll r_){
		l=l_,r=r_;
	}
	bool operator<(const node&y)const{
		if(l==y.l)return r<y.r;
		return l<y.l;
	}
};
multiset<node>s;
ll a[200005];
int son[200005][2],fath[200005],rt,tt,n,q,cnt;
void ins(ll l,ll r){
	if(l>r)swap(l,r);
	sit it=s.lower_bound(node(l,r));
	if(it!=s.begin()&&it!=s.end()){
		sit it1=it;it1--;
		if((*it1).r>(*it).l)cnt--;
	}
	s.insert(node(l,r));
	it=s.lower_bound(node(l,r));
	sit it1=it;it1++;
	if(it1!=s.end()){
		if((*it).r>(*it1).l)cnt++;
	}
	if(it!=s.begin()){
		it1=it;it1--;
		if((*it1).r>(*it).l)cnt++;
	}
}
void del(ll l,ll r){
	if(l>r)swap(l,r);
	sit it=s.lower_bound(node(l,r));
	sit it1=it;it1++;
	if(it1!=s.end()){
		if((*it).r>(*it1).l)cnt--;
	}
	if(it!=s.begin()){
		it1=it;it1--;
		if((*it1).r>(*it).l)cnt--;
	}
	s.erase(it);
	it=s.lower_bound(node(l,r));
	if(it!=s.begin()&&it!=s.end()){
		it1=it;it1--;
		if((*it1).r>(*it).l)cnt++;
	}
}
int mx;
void dfs(int now,int dep){
	if(now<=n)return;
	mx=max(dep,mx);
	dfs(son[now][0],dep+1),dfs(son[now][1],dep+1);
	ins(a[son[now][0]],a[son[now][1]]);
	a[now]=a[son[now][0]]+a[son[now][1]];
}
void upd(int x,ll v){
	int tmp=x;
	while(x!=rt){
		x=fath[x];
		del(a[son[x][0]],a[son[x][1]]);
	}
	x=tmp;
	a[x]=v;
	while(x!=rt){
		x=fath[x];
		a[x]=a[son[x][0]]+a[son[x][1]];
		ins(a[son[x][0]],a[son[x][1]]);
	}
}
int main(){
	fin.read(n,q);q--;
	for(int i=1;i<=n;i++)fin.read(a[i]);
	for(int i=n+1;i<n+n;i++){
		fin.read(son[i][0],son[i][1]);
		fath[son[i][0]]=fath[son[i][1]]=i;
	}
	for(int i=n+1;i<n+n;i++){
		if(!fath[i])rt=i;
	}
	dfs(rt,1);
	if(mx>75){
		for(int i=0;i<=q;i++)fout.write("NO\n");
		return 0;
	}
	if(cnt==0)fout.write("YES\n");
	else fout.write("NO\n");
	while(q--){
		int x;ll v;fin.read(x,v);
		upd(x,v);
		if(cnt==0)fout.write("YES\n");
		else fout.write("NO\n");
	}
	return 0;
}
Source code, Language: C++14

Details 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:4:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

Server Time: 2025-01-10 18:55:55 | OpenSource Project