304 North Cardinal St.
Dorchester Center, MA 02124

# Crease Painting CodeChef Solution

## Crease Painting CodeChef Solution in C++14

``````
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <map>
#include <cassert>
#define mod  1000000007
#define PHI 1000000006
#define ull unsigned long long
#define ll long long int
#define pii pair<int,int>
#define pb(x) push_back(x)
#define F(i,a,n) for(i=(a);i<(n);++i)
#define FD(i,a,n) for(i=(a);i>=(n);--i)
#define FE(it,x) for(it=x.begin();it!=x.end();++it)
#define V(x) vector<x>
#define S(x) scanf("%d",&x)
#define S1(x) scanf("%llu",&x)
#define MAX 50009
#define NIL 0
#define INF (1<<28)

#define MAXNODES 50009
using namespace std;

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
ll startx[1002];
ll endx[1002];
ll starty[1002];
ll endy[1002];
void intersect(ll sx1,ll sy1,ll ex1,ll ey1,ll sx2,ll sy2,ll ex2,ll ey2, vector<pair<ll,ll> >* segments)
{
if(sx2==ex2)
{
if(sx1!=sx2)
return;
ll sy3=max(min(sy1,ey1),min(sy2,ey2));
ll ey3=min(max(sy1,ey1),max(sy2,ey2));
if(sy3>ey3)
return;
segments->push_back(make_pair(sy3,ey3));
return;
}
if(sy2==ey2)
{
if(sy2>=min(sy1,ey1) && sy2<=max(sy1,ey1) && min(sx2,ex2)<=sx1 && max(sx2,ex2)>=sx1)
segments->push_back(make_pair(sy2,sy2));
return;
}
}
map<pair<int,int>,bool> hashed;
int main()
{
int N;
scanf("%d",&N);
ll cx=0;
ll cy=0;
startx[0]=endx[0]=starty[0]=endy[0]=0;
for(int i=1;i<=N;i++)
{
char dir[3];
ll steps;
int id;
scanf("%s",&dir);
scanf("%lld",&steps);
if(dir[0]=='R')
id=0;
if(dir[0]=='L')
id=1;
if(dir[0]=='U')
id=2;
if(dir[0]=='D')
id=3;
startx[i]=cx+dx[id];
starty[i]=cy+dy[id];
endx[i]=cx+dx[id]*steps;
endy[i]=cy+dy[id]*steps;

cx=endx[i];
cy=endy[i];
vector<pair<ll,ll> > segments;
for(int j=0;j<i;j++)
{
if(startx[i]==endx[i])
intersect(startx[i],starty[i],endx[i],endy[i],startx[j],starty[j],endx[j],endy[j],&segments);
else
intersect(starty[i],startx[i],endy[i],endx[i],starty[j],startx[j],endy[j],endx[j],&segments);
}
sort(segments.begin(),segments.end());
ll st=(startx[i]==endx[i]?min(starty[i],endy[i]):min(startx[i],endx[i]));
ll en=(startx[i]==endx[i]?max(starty[i],endy[i]):max(startx[i],endx[i]));
ll currocc=en-st+1;
for(int j=0;j<segments.size();j++)
{
currocc-=max(0ll,(segments[j].second-max(st,segments[j].first))+1);
st=max(st,segments[j].second+1);
}
printf("%lld\n",currocc);
}
}``````

## Crease Painting CodeChef Solution in JAVA

``````import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve()
{
int n = ni();
int[][] pa = new int[n][];
for(int i = 0;i < n;i++){
int c = nc();
int d = ni();
pa[i] = new int[]{c, d};
}
long x = 0, y = 0;
long[][] co = new long[n][];
for(int i = 0;i < n;i++){
int c = pa[i][0], d = pa[i][1];
if(c == 'U'){
co[i] = new long[]{x, y, x+1, y+1+d};
y += d;
}else if(c == 'D'){
co[i] = new long[]{x, y-d, x+1, y+1};
y -= d;
}else if(c == 'R'){
co[i] = new long[]{x, y, x+1+d, y+1};
x += d;
}else{
co[i] = new long[]{x-d, y, x+1, y+1};
x -= d;
}
}

long[] shx = new long[2*n];
for(int i = 0;i < n;i++){
shx[2*i] = co[i][0];
shx[2*i+1] = co[i][2];
}
Object[] resx = shrink(shx);
int[] shedx = (int[])resx[0];
long[] ix = (long[])resx[1];

long[] shy = new long[2*n];
for(int i = 0;i < n;i++){
shy[2*i] = co[i][1];
shy[2*i+1] = co[i][3];
}
Object[] resy = shrink(shy);
int[] shedy = (int[])resy[0];
long[] iy = (long[])resy[1];

boolean[][] F = new boolean[ix.length][iy.length];
for(int i = 0;i < n;i++){
long S = 0;
for(int j = shedx[2*i];j < shedx[2*i+1];j++){
for(int k = shedy[2*i];k < shedy[2*i+1];k++){
if(!F[j][k]){
F[j][k] = true;
S += ix[j] * iy[k];
}
}
}
if(i == 0)S--;
out.println(S);
}
}

public static Object[] shrink(final long[] a)
{
int n = a.length;
Integer[] b = new Integer[n];
for(int i = 0;i < n;i++)b[i] = i;
Arrays.sort(b, new Comparator<Integer>(){
public int compare(Integer x, Integer y){
return Long.signum(a[x] - a[y]);
}
});
int[] ret = new int[n];
long[] interval = new long[n];
int p = 0;
for(int i = 0;i < n;i++){
if(i > 0 && a[b[i]] > a[b[i-1]]){
interval[p] = a[b[i]]-a[b[i-1]];
p++;
}
ret[b[i]] = p;
}

return new Object[]{ret, Arrays.copyOf(interval, p)};
}

static char nc()
{
try {
int b;
while((b = is.read()) != -1 && (b == ' ' || b == '\r' || b == '\n'));
if(b == -1)return 0;
return (char)b;
} catch (IOException e) {
}
return 0;
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

static boolean eof()
{
try {
is.mark(1000);
int b;
while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
is.reset();
return b == -1;
} catch (IOException e) {
return true;
}
}

static int ni()
{
try {
int num = 0;
boolean minus = false;
while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
if(num == '-'){
num = 0;
minus = true;
}else{
num -= '0';
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}

static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}``````

## Crease Painting CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
"sort"
)

func main() {

S := make([]string, n)

for i := 0; i < n; i++ {
}

res := solve(n, S)

var buf bytes.Buffer

for i := 0; i < n; i++ {
buf.WriteString(fmt.Sprintf("%d\n", res[i]))
}

fmt.Print(buf.String())
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

func solve(n int, commands []string) []int {
ans := make([]int, n)

var x, y int64

strips := make([]Stripe, n+1)
strips[0] = Stripe{0, 0, 0, 0}

for i := 0; i < n; i++ {
cmd := parseCommand(commands[i])

if cmd.dir == 'L' {
strips[i+1] = NewStripe(x-1, y, x-cmd.dis, y)
x -= cmd.dis
} else if cmd.dir == 'R' {
strips[i+1] = NewStripe(x+1, y, x+cmd.dis, y)
x += cmd.dis
} else if cmd.dir == 'U' {
strips[i+1] = NewStripe(x, y+1, x, y+cmd.dis)
y += cmd.dis
} else {
strips[i+1] = NewStripe(x, y-1, x, y-cmd.dis)
y -= cmd.dis
}

var horizontal bool
if cmd.dir == 'L' || cmd.dir == 'R' {
horizontal = true
}
var ps []Point
for j := 0; j <= i; j++ {
ok, intersection := intersect(strips[i+1], strips[j])

if ok {
if horizontal {
ps = append(ps, Point{intersection.x1 - strips[i].x1, false})
ps = append(ps, Point{intersection.x2 - strips[i].x1 + 1, true})
} else {
ps = append(ps, Point{intersection.y1 - strips[i].y1, false})
ps = append(ps, Point{intersection.y2 - strips[i].y1 + 1, true})
}
}
}

sort.Sort(Points(ps))

var covered int
var last int64
var painted = cmd.dis

for j := 0; j < len(ps); j++ {
p := ps[j]
if covered > 0 {
painted -= p.coord - last
}
if p.begin {
covered--
} else {
covered++
}
last = p.coord
}
ans[i] = int(painted)
}

return ans
}

type Stripe struct {
x1, y1, x2, y2 int64
}

func NewStripe(x1, y1, x2, y2 int64) Stripe {
return Stripe{min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)}
}

func intersect(a, b Stripe) (bool, Stripe) {
x1 := max(a.x1, b.x1)
y1 := max(a.y1, b.y1)
x2 := min(a.x2, b.x2)
y2 := min(a.y2, b.y2)
if x1 > x2 || y1 > y2 {
return false, Stripe{}
}
return true, Stripe{x1, y1, x2, y2}
}

type Point struct {
coord int64
begin bool
}

func (this Point) Less(that Point) bool {
if this.coord != that.coord {
return this.coord < that.coord
}
if this.begin != that.begin {
return !this.begin
}
return false
}

type Points []Point

func (this Points) Len() int {
return len(this)
}

func (this Points) Less(i, j int) bool {
return this[i].Less(this[j])
}

func (this Points) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}

func min(a, b int64) int64 {
if a <= b {
return a
}
return b
}

func max(a, b int64) int64 {
if a >= b {
return a
}
return b
}

type Command struct {
dir byte
dis int64
}

func parseCommand(s string) *Command {
dir := s[0]
var dis int
return &Command{dir, int64(dis)}
}``````
##### Crease Painting CodeChef Solution Review:

In our experience, we suggest you solve this Crease Painting CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Crease Painting CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Crease Painting CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!