Submission #98656

#	Time	Username	Problem	Language	Result	Execution time	Memory
98656		LittleFlowers__	Topovi (COCI15_topovi)	C++14	6 / 120	2087 ms	26300 KiB

topovi

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
inline void out(long long x){if(x<0) putchar('-'),x=-x;if(x>9) out(x/10);putchar(x%10+'0');}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define task "TOPOVI"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
//brute
const int N=100010;

int n,k,p;
int val[N];
ii pos[N];
struct{int x1,y1,x2,y2;}query[N];

vector<int> x,y;
int xv[N],yv[N],ox[N],oy[N];
map<ii,int> mp;

int posin(const vector<int>&x,int y)
{
    return lower_bound(all(x),y)-x.begin()+1;
}

void build()
{
    forinc(t,1,k)
    {
        int i=posin(x,pos[t].fi);
        int j=posin(y,pos[t].se);

        xv[i]^=val[t];
        yv[j]^=val[t];

        ox[i]++;
        oy[j]++;

        mp[{i,j}]=t;
    }
}

void change(int t)
{
    int i1=posin(x,query[t].x1);
    int j1=posin(y,query[t].y1);
    int i2=posin(x,query[t].x2);
    int j2=posin(y,query[t].y2);

    int id=mp[{i1,j1}];

    xv[i1]^=val[id];
    yv[j1]^=val[id];

    ox[i1]--,oy[j1]--;

    xv[i2]^=val[id];
    yv[j2]^=val[id];

    ox[i2]++,oy[j2]++;

    mp[{i2,j2}]=id;
    mp[{i1,j1}]=0;

}

int solve()
{
    int ret=n*n,cx=0,cy=0;

    forinc(i,1,x.size()) cx+=(!!xv[i]);
    forinc(i,1,y.size()) cy+=(!!yv[i]);

    ret-=(n-cx)*(n-cy);

    forinc(i,1,x.size()) if(ox[i])
    {
        forinc(j,1,y.size()) if(oy[j] && xv[i]==yv[j])
            ret--;
    }
    return ret;
}

main()
{
    //freopen(task".inp","r",stdin);
    n=in,k=in,p=in;
    forinc(i,1,k) pos[i]={in,in},val[i]=in;
    forinc(i,1,p) query[i]={in,in,in,in};

    forinc(i,1,k)
    {
        x.pb(pos[i].fi);
        y.pb(pos[i].se);
    }
    forinc(i,1,p)
    {
        x.pb(query[i].x1);
        x.pb(query[i].x2);
        y.pb(query[i].y1);
        y.pb(query[i].y2);
    }

    sort(all(x)),x.erase(unique(all(x)),x.end());
    sort(all(y)),y.erase(unique(all(y)),y.end());

    build();
    forinc(i,1,p)
    {
        change(i);
        cout<<solve()<<"\n";
    }
}

Compilation message (stderr)

topovi.cpp:95:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 6 / 120